2212: [Poi2011]Tree Rotations

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 ;
}
上一篇:cubieboard安装小记


下一篇:栅格那点儿事(四C)