2212: [Poi2011]Tree Rotations

这题其实是道水题。。平衡树的启发式合并。总的逆序对个数=左子树的+右子树的+左子树与右子树之间的。。

然后暴力合并。。每次合并时计算左右子树间的逆序对，而左右子树的之前已经递归求好了。。这次得了个教训，果然旋转还是比不旋转强= =！

#include<cstdio>
typedef long long ll;
struct re{
    int n,c[3],f;
    long long s;
} t[300001];
int n,sum=0,s=0;
ll ans=0,ss=0;
int root[1000001];
ll min(ll a,ll b){return a<b? a:b;}
void update(int x){
    t[x].s=t[t[x].c[1]].s+1+t[t[x].c[2]].s;
}
void ro(int x,int w){
    int y=t[x].f;
    int ww=3-w;
    t[y].c[ww]=t[x].c[w];
    if (t[x].c[w]) t[t[x].c[w]].f=y;
    t[x].f=t[y].f;
    if (t[y].f){
        int z=t[y].f;
        if (y==t[z].c[1]) t[z].c[1]=x;
        else t[z].c[2]=x;
    }
    t[y].f=x;
    t[x].c[w]=y;
    update(y);
}
void splay(int i,int x){
    while (t[x].f){
        int y=t[x].f;
        if (!t[y].f){
            if (x==t[y].c[1]) ro(x,2);
            else ro(x,1);
        }else{
            int z=t[y].f;
            if (y==t[z].c[1]){
                if (x==t[y].c[1]){ro(y,2);  ro(x,2);}
                else {ro(x,1);  ro(x,2);}
            }else{
                if (x==t[y].c[2]){ro(y,1);  ro(x,1);}
                else {ro(x,2);  ro(x,1);}
            }
        }
    }
    update(x);
    if (!t[x].f) root[i]=x;
}
void inse(int i,int x,int y){
    ll su=0;
    while (true){
        t[x].s++;
        if ((t[y].n<t[x].n&&t[x].c[1]==0)||(t[y].n>t[x].n&&t[x].c[2]==0)) break;
        if (t[y].n<t[x].n) x=t[x].c[1];
        else {su+=t[t[x].c[1]].s+1; x=t[x].c[2];}
    }
    if (t[y].n<t[x].n)   t[x].c[1]=y;
    else{su+=t[t[x].c[1]].s+1; t[x].c[2]=y;}
    t[y].f=x;
    ss+=su;
    splay(i,y);
}
void uniont(int i,int x){
    int l=t[x].c[1],r=t[x].c[2];
    if (r) uniont(i,r);
    t[x].f=t[x].c[1]=t[x].c[2]=0;
    t[x].s=1;
    inse(i,root[i],x);
    if (l) uniont(i,l);
}
void combine(int k,int i,int j){
    int x=root[i];
    int y=root[j];
    if (t[x].s<t[y].s){
        uniont(j,root[i]);
        root[k]=root[j];
    }else{
        uniont(i,root[j]);
        root[k]=root[i];
    }
}
void dfs(int i){
    int x;
    scanf("%d",&x);
    if (x!=0){
        t[++sum].n=x;
        t[sum].s=1;
        root[i]=sum;
        return;
    }
    int l=++s,r=++s;
    dfs(l);
    dfs(r);
    ss=0;
    ll sa=t[root[l]].s*t[root[r]].s;
    combine(i,l,r);
    ans+=min(ss,sa-ss);
}
int main(){
    scanf("%d",&n);
    s=1;
    dfs(1);
    printf("%lld\n",ans);
}