题解 P3521 【[POI2011]ROT-Tree Rotations】

· · 题解

输入格式真的毒瘤

权值线段树合并。

我们先对每一个叶子建一棵权值线段树，并把它自己的权值插入到里面。然后不断的向上合并。

我们不妨设原树中当前节点为 u，爸爸 fa，左儿子 lc，右儿子 rc，那么显然这棵树中的逆序对分为 3 个部分：lc 里的逆序对，rc 里的逆序对和跨 lc 和 rc 的逆序对。

而我们现在已经把 lc 里的逆序对和 rc 里的逆序对算好了，现在需要求出跨 lc 和 rc 的逆序对，也就是合并 lc 和 rc 。然后我们发现，无论 lc 内的子树怎么换来换去，rc内的子树怎么换来换去，都是对跨 lc 和 rc 的逆序对个数没有影响的。

同理，无论我们交不交换 lc 和 rc，对 fa 那一层的合并也是没有影响的。

所以对于跨 lc 和 rc 的逆序对，我们分交换 lc、rc 和不交换的情况算出两种情况的逆序对个数，再取较小值就好了。

我们遍历两棵权值线段树来暴力合并两棵权值线段树。

那么对于 lc 和 rc 权值线段树中同一位置的点 a、b，若不交换 lc 和 rc，显然 lc 中的点的编号（这里的编号是指前序遍历的先后顺序）肯定都在 rc 前，a 右儿子的权值必定大于 b 左儿子的权值，所以 size[ch[a][1]]*size[ch[b][0]] 就是这一位置的答案了。

同理，如果交换 lc 和 rc，这一位置的答案就是 size[ch[a][0]]*size[ch[b][1]]。

最后合并完统计答案即可。

代码如下：

#include<bits/stdc++.h>

#define N 200010
#define int long long

using namespace std;

struct Tree
{
    int ch[2],size;
}t[N<<5];

int n,tot,ans,num1,num2;

int update(int l,int r,int val)
{
    int u=++tot;
    t[u].size=1;
    if(l==r) return u;
    int mid=(l+r)>>1;
    if(val<=mid) t[u].ch[0]=update(l,mid,val);
    else t[u].ch[1]=update(mid+1,r,val);
    return u;
}

int merge(int a,int b,int l,int r)//把b合并至a
{
    if(!a||!b) return a+b;
    if(l==r)
    {
        t[a].size+=t[b].size;
        return a;
    }
    num1+=t[t[a].ch[1]].size*t[t[b].ch[0]].size;//不交换的答案
    num2+=t[t[b].ch[1]].size*t[t[a].ch[0]].size;//交换后的答案
    int mid=(l+r)>>1;
    t[a].ch[0]=merge(t[a].ch[0],t[b].ch[0],l,mid);
    t[a].ch[1]=merge(t[a].ch[1],t[b].ch[1],mid+1,r);
    t[a].size+=t[b].size;
    return a;
}

int dfs()
{
    int u,val;
    scanf("%lld",&val);
    if(!val)
    {
        int lc=dfs(),rc=dfs();
        num1=num2=0;
        u=merge(lc,rc,1,n);
        ans+=min(num1,num2);//ans加上较小值
    }
    else u=update(1,n,val);
    return u;
}

signed main()
{
    scanf("%lld",&n);
    dfs();
    printf("%lld\n",ans);
    return 0;
}