BZOJ2212：[POI2011]Tree Rotation

浅谈线段树合并：https://www.cnblogs.com/AKMer/p/10251001.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=2212

递归去做，统计每个子树内最少会产生多少逆序对，在合并线段树的时候统计就好了。

代码如下：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=2e5+5;

int n,tot;
ll ans,cnt1,cnt2;
int rt[maxn<<1],ls[maxn<<1],rs[maxn<<1];

int read() {
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
    return x*f;
}

struct segment_tree {
    int tot;
    int sum[maxn*20],ls[maxn*20],rs[maxn*20];

    void update(int p) {
        sum[p]=sum[ls[p]]+sum[rs[p]];
    }

    void change(int &p,int l,int r,int pos) {
        p=++tot;
        if(l==r) {sum[p]=1;return;}
        int mid=(l+r)>>1;
        if(pos<=mid)change(ls[p],l,mid,pos);
        else change(rs[p],mid+1,r,pos);
        update(p);
    }

    int merge(int a,int b) {
        if(!a||!b)return a+b;
        cnt1+=1ll*sum[rs[a]]*sum[ls[b]];//cnt1记录不交换左右子树会得到多少逆序对
        cnt2+=1ll*sum[rs[b]]*sum[ls[a]];//cnt2记录交换左右子树会得到多少逆序对
        ls[a]=merge(ls[a],ls[b]);
        rs[a]=merge(rs[a],rs[b]);
        update(a);return a;
    }
}T;

void solve(int u) {
    int x=read();
    if(x)T.change(rt[u],1,n,x);
    else {
        ls[u]=++tot,solve(ls[u]);
        rs[u]=++tot,solve(rs[u]);
        cnt1=cnt2=0;
        rt[u]=T.merge(rt[ls[u]],rt[rs[u]]);
        ans+=min(cnt1,cnt2);
    }
}

int main() {
    n=read();
    solve(1);
    printf("%lld\n",ans);
    return 0;
}

BZOJ2212：[POI2011]Tree Rotation

原文：https://www.cnblogs.com/AKMer/p/10252305.html