2212: [Poi2011]Tree Rotations

https://www.lydsy.com/JudgeOnline/problem.php?id=2212

分析：

　　线段树合并。

　　首先对每个节点建立一棵权值线段树，然后遍历整棵树，从叶子节点开始合并，每次合并两个节点的主席树，判断是否交换这两个节点，求出这两个节点分在前面所形成的逆序对。

　　求逆序对：对于主席树中的右子树一定比左子树大，所以每次合并一个节点时，直接用右子树的个数乘以左子树的个数，不断递归。

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<cctype>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<map>
11 #define fi(s) freopen(s,"r",stdin);
12 #define fo(s) freopen(s,"w",stdout);
13 using namespace std;
14 typedef long long LL;
15 
16 inline int read() {
17     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
18     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
19 }
20 
21 const int N = 200005;
22 
23 int A[N << 1], T[N << 1][2], Root[N << 1], sum[N * 20], ls[N * 20], rs[N * 20];
24 int Index, tot, Rt;
25 LL Ans, Ans0, Ans1;
26 
27 void ReadTree(int &x) {
28     x = ++Index;
29     A[x] = read();
30     if (A[x]) return ;
31     ReadTree(T[x][0]); 
32     ReadTree(T[x][1]);
33 }
34 
35 void Insert(int l,int r,int &rt,int p) {
36     rt = ++tot;
37     sum[rt] = 1;
38     if (l == r) return ;
39     int mid = (l + r) >> 1;
40     if (p <= mid) Insert(l, mid, ls[rt], p);
41     else Insert(mid + 1, r, rs[rt], p);
42 }
43 
44 int Merge(int x,int y) { // 合并x y 
45     if (!x || !y) return x + y;
46     Ans0 += 1ll * sum[rs[x]] * sum[ls[y]]; // x在前 
47     Ans1 += 1ll * sum[rs[y]] * sum[ls[x]]; // y在前 
48     ls[x] = Merge(ls[x], ls[y]);
49     rs[x] = Merge(rs[x], rs[y]);
50     sum[x] += sum[y];
51     return x;
52 }
53 
54 void solve(int x) {
55     if (A[x]) return ;
56     solve(T[x][0]); solve(T[x][1]);
57     Ans0 = 0, Ans1 = 0;
58     Root[x] = Merge(Root[T[x][0]], Root[T[x][1]]);
59     Ans += min(Ans0, Ans1);    
60 }
61 
62 int main() {
63     
64     int n = read();
65     ReadTree(Rt);
66     for (int i=1; i<=Index; ++i) 
67         if (A[i]) Insert(1, n, Root[i], A[i]);
68     solve(Rt);
69     cout << Ans << endl;
70     return 0;
71 }