BZOJ2212 [Poi2011]Tree Rotations 线段树合并 逆序对 题目传送门 - BZOJ2212 题意概括 题解 代码
原文链接http://www.cnblogs.com/zhouzhendong/p/8079786.html
题意概括
给一棵n(1≤n≤200000个叶子的二叉树，可以交换每个点的左右子树，要求前序遍历叶子的逆序对最少。
题解
线段树合并。
博主很懒，题解不写了。
这份代码是仿照别人的写的。
代码
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long LL;
const int N=200005;
int n,val[N*2],son[N*2][2],tot=0,rt;
int root[N*2],ls[N*2*20],rs[N*2*20];
LL sum[N*2*20];
void dfsread(int &x){
x=++tot;
scanf("%d",&val[x]);
if (!val[x]){
dfsread(son[x][0]);
dfsread(son[x][1]);
}
}
void pushup(int rt){
sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
LL sumL,sumR;
void add(int &rt,int L,int R,int v){
rt=++tot;
int mid=(L+R)>>1;
if (L==R){
sum[rt]=1;
return;
}
if (v<=mid)
add(ls[rt],L,mid,v);
else
add(rs[rt],mid+1,R,v);
pushup(rt);
}
int merge(int a,int b){
if (!a||!b)
return a+b;
sumL+=sum[rs[a]]*sum[ls[b]];
sumR+=sum[ls[a]]*sum[rs[b]];
ls[a]=merge(ls[a],ls[b]);
rs[a]=merge(rs[a],rs[b]);
pushup(a);
return a;
}
LL dfs(int x){
LL ans=0;
if (!val[x]){
ans=dfs(son[x][0])+dfs(son[x][1]);
sumL=sumR=0;
root[x]=merge(root[son[x][0]],root[son[x][1]]);
ans+=min(sumL,sumR);
}
else
add(root[x],1,n,val[x]);
return ans;
}
int main(){
scanf("%d",&n);
dfsread(rt);
printf("%lld",dfs(rt));
return 0;
}