P3521 [POI2011]ROT-Tree Rotations （线段树合并）

本文主要是介绍P3521 [POI2011]ROT-Tree Rotations （线段树合并），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

对于一个非叶节点，不管是否要交换子树，其左右子树内部的逆序对数都不会受影响（内部的顺序并不会影响外部产生的逆序对数），受影响的是跨左右子树的情况，所以我们考虑统计这一部分的逆序对数。节点x的左右子树根节点为p，q，u+=size[t[p].rc] * size[t[q].lc]，交换后 v+=size[t[p].lc]*size[t[q].rc]。

这道题的输入处理有些毒瘤（我还是第一次见），他让我们递归，那我们就递归求解，对于每个叶节点建立一颗权值线段树，不断向上合并，每次合并递归到线段树的所有非叶节点，按照上面的方式累加u和v，最后取min加入答案之中。

（画图模拟一下过程更好理解）

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 const int N = 2e5+10;
 4 using namespace std;
 5 struct node {
 6     int lc, rc, sze;
 7 }tr[22 * N];//N*logN的空间 
 8 int n, top;
 9 ll ans, u, v;
10 
11 int read() {//快读 
12     int x = 0; char ch = getchar();
13     while(ch > '9' || ch < '0') ch = getchar();
14     while(ch >= '0'&&ch <= '9') x = x * 10 + ch - '0', ch = getchar();
15     return x;
16 }
17 
18 int update(int l, int r, int val) {
19     int pos = ++top;
20     tr[top].sze++;
21     if (l == r) return pos;
22     int mid = (l + r) >> 1;
23     if (val <= mid) tr[pos].lc = update(l, mid, val);
24     else tr[pos].rc = update(mid + 1, r, val);
25     return pos;
26 } 
27 
28 int merge(int p, int q, int l, int r) {
29     if(!p || !q) return p + q;
30     if (l == r) {
31         tr[p].sze += tr[q].sze;
32         return p;
33     }
34     u += (ll)tr[tr[p].rc].sze * tr[tr[q].lc].sze;//交换前 
35     v += (ll)tr[tr[p].lc].sze * tr[tr[q].rc].sze;//交换后
36     int mid = (l + r) >> 1;
37     tr[p].lc = merge(tr[p].lc, tr[q].lc, l, mid);
38     tr[p].rc = merge(tr[p].rc, tr[q].rc, mid + 1, r); 
39     tr[p].sze = tr[tr[p].lc].sze + tr[tr[p].rc].sze;
40     return p;
41 }
42 
43 int dfs() {
44     int pos, val = read();
45     if (val == 0) {
46         int ls = dfs(), rs = dfs();
47         u = 0, v = 0;
48         pos = merge(ls, rs, 1, n);
49         ans += min(u, v);
50     }
51     else pos = update(1, n, val);//对叶子节点建树 
52     return pos; 
53 }
54 
55 int main() {
56     n = read();
57     dfs();
58     printf("%lld", ans);
59     return 0;
60 }

这篇关于P3521 [POI2011]ROT-Tree Rotations （线段树合并）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！