luogu P3521 [POI2011]ROT-Tree Rotations

思路

合并时候统计逆序对贡献

代码

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define ll long long
using namespace std;
const int maxn=2e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,cnt;
ll ans,ans1,ans2;
struct edge {
    int ch[2],siz;
}e[maxn*30];
void build(int &now,int l,int r,int k) {
    now=++cnt;e[now].siz++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(k<=mid) build(e[now].ch[0],l,mid,k);
    else build(e[now].ch[1],mid+1,r,k);
}
int merge(int x,int y) {
    if(!x || !y) return x+y;
    e[x].siz+=e[y].siz;
    ans1+=1LL*e[e[x].ch[0]].siz*e[e[y].ch[1]].siz;
    ans2+=1LL*e[e[x].ch[1]].siz*e[e[y].ch[0]].siz;
    e[x].ch[0]=merge(e[x].ch[0],e[y].ch[0]);
    e[x].ch[1]=merge(e[x].ch[1],e[y].ch[1]);
    return x;
}
int dfs() {
    int tmp=read(),x=0;
    if(!tmp) {
        int ls=dfs(),rs=dfs();
        x=merge(ls,rs);
        ans+=min(ans1,ans2);
        ans1=ans2=0;
    }
    else build(x,1,n,tmp);
    return x;
}
int main() {
    n=read();
    dfs();
    cout<<ans<<"\n";
    return 0;
}