2212: [Poi2011]Tree Rotations

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

分析：

线段树合并。

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

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

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int A[N << ], T[N << ][], Root[N << ], sum[N * ], ls[N * ], rs[N * ];

 int Index, tot, Rt;

 LL Ans, Ans0, Ans1;

 void ReadTree(int &x) {

     x = ++Index;

     A[x] = read();

     if (A[x]) return ;

     ReadTree(T[x][]);

     ReadTree(T[x][]);

 }

 void Insert(int l,int r,int &rt,int p) {

     rt = ++tot;

     sum[rt] = ;

     if (l == r) return ;

     int mid = (l + r) >> ;

     if (p <= mid) Insert(l, mid, ls[rt], p);

     else Insert(mid + , r, rs[rt], p);

 }

 int Merge(int x,int y) { // 合并x y

     if (!x || !y) return x + y;

     Ans0 += 1ll * sum[rs[x]] * sum[ls[y]]; // x在前

     Ans1 += 1ll * sum[rs[y]] * sum[ls[x]]; // y在前

     ls[x] = Merge(ls[x], ls[y]);

     rs[x] = Merge(rs[x], rs[y]);

     sum[x] += sum[y];

     return x;

 }

 void solve(int x) {

     if (A[x]) return ;

     solve(T[x][]); solve(T[x][]);

     Ans0 = , Ans1 = ;

     Root[x] = Merge(Root[T[x][]], Root[T[x][]]);

     Ans += min(Ans0, Ans1);

 }

 int main() {

     int n = read();

     ReadTree(Rt);

     for (int i=; i<=Index; ++i)

         if (A[i]) Insert(, n, Root[i], A[i]);

     solve(Rt);

     cout << Ans << endl;

     return ;

 }