BZOJ2212:[Poi2011]Tree Rotations 平衡树启发式合并

思路:

显然左右子树内的逆序对并不会互相影响,那么会产生影响的仅仅是是否交换左右子树.

我们利用平衡树启发式合并,每一次用小的平衡树在大的平衡树里面询问小的有多少以及大的有多少决定是否交换.

然后暴力将小的平衡树合并到大的平衡树里面.

(貌似还可以用线段树启发式合并?不过我并不想写,虽然常数小)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

#define l ch[0]
#define r ch[1]

#define N 200010
struct Node{
	Node*ch[2];
	int v,siz,pr;
	Node():siz(0){}
	inline void up(){siz=l->siz+r->siz+1;}
}mem[4000010],*C=mem,Tnull,*null=&Tnull;
inline Node*Newnode(int _v){
	C->l=C->r=null;C->v=_v,C->siz=1,C->pr=rand();return C++;
}
inline void Rot(Node*&p,bool d){
	Node*q=p->ch[!d];p->ch[!d]=q->ch[d],q->ch[d]=p,p->up(),q->up(),p=q;
}
inline void Insert(Node*&p,int x){
	if(p==null){p=Newnode(x);return;}
	if(x<p->v){Insert(p->l,x);if(p->l->pr<p->pr)Rot(p,1);}
	else{Insert(p->r,x);if(p->r->pr<p->pr)Rot(p,0);}
	p->up();
}
inline int QueryLess(Node*p,int x){
	if(p==null)return 0;
	if(p->v>x)return QueryLess(p->l,x);
	else return p->l->siz+1+QueryLess(p->r,x);
}
inline int QueryMore(Node*p,int x){
	if(p==null)return 0;
	if(p->v<x)return QueryMore(p->r,x);
	else return p->r->siz+1+QueryMore(p->l,x);
}

int L[N<<1],R[N<<1],cnt,x,w[N<<1];
inline int read(){
	int q=++cnt;
	scanf("%d",&x);
	if(!x)L[q]=read(),R[q]=read();else w[q]=x;
	return q;
}

LL res=0,tans1,tans2;

Node*Root[N<<1];
static Node*q[N<<1];int fr,ta;
void dfs(int x){
	if(w[x]){Root[x]=Newnode(w[x]);return;}
	dfs(L[x]),dfs(R[x]);
	tans1=tans2=0;
	if(Root[L[x]]->siz<Root[R[x]]->siz){
		fr=ta=0;q[ta++]=Root[L[x]];
		while(fr^ta){
			Node*p=q[fr++];
			tans1+=QueryLess(Root[R[x]],p->v),tans2+=QueryMore(Root[R[x]],p->v);
			if(p->l!=null)q[ta++]=p->l;if(p->r!=null)q[ta++]=p->r;
		}
		res+=min(tans1,tans2);
		fr=ta=0;q[ta++]=Root[L[x]];
		while(fr^ta){
			Node*p=q[fr++];
			Insert(Root[R[x]],p->v);
			if(p->l!=null)q[ta++]=p->l;if(p->r!=null)q[ta++]=p->r;
		}
		Root[x]=Root[R[x]];
	}
	else{
		fr=ta=0;q[ta++]=Root[R[x]];
		while(fr^ta){
			Node*p=q[fr++];
			tans1+=QueryLess(Root[L[x]],p->v),tans2+=QueryMore(Root[L[x]],p->v);
			if(p->l!=null)q[ta++]=p->l;if(p->r!=null)q[ta++]=p->r;
		}
		res+=min(tans1,tans2);
		fr=ta=0;q[ta++]=Root[R[x]];
		while(fr^ta){
			Node*p=q[fr++];
			Insert(Root[L[x]],p->v);
			if(p->l!=null)q[ta++]=p->l;if(p->r!=null)q[ta++]=p->r;
		}
		Root[x]=Root[L[x]];
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	scanf("%d",&x);read();
	
	dfs(1);
	
	cout<<res<<endl;
	
	return 0;
}