「POI2011」Tree Rotations-线段树合并

现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点,满足这些权值为1-n的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换,使得最终所有叶子节点的权值按照前序遍历序写出来,逆序对个数最少。

输入解释:
第一行一个数n,表示该二叉树的叶节点的个数;
下面若干行,每行一个数 x
如果x = 0,表示这个节点不是叶节点,递归地向下读入其左孩子和右孩子的信息;
如果x ≠ 0,表示这个节点是叶节点,权值为x

题解:
采用线段树合并,只是在线段树合并的时候考虑左右子树对应的权值线段树,是否进行交换,然后计算一下逆序对数量。

#include <bits/stdc++.h>

const int MAXN = 10000000;

using namespace std;

int n,sz,dfn;
int rt[MAXN],sum[MAXN],ls[MAXN],rs[MAXN];
long long ans,u,v;

void update(int &o,int L,int R){
    if(!o) o = ++sz;
    sum[o]++;
    if(L == R) return;
    int M = (L + R) >> 1;
    if(v <= M) update(ls[o],L,M);
    else update(rs[o],M+1,R);
    
}

int merge(int x,int y,int L,int R){
    if(!x || !y) return x + y;
    if(L == R){
        sum[x] += sum[y];
        return x;
    }
    u += 1ll*sum[ls[x]]*sum[rs[y]];//交换前
    v += 1ll*sum[ls[y]]*sum[rs[x]];//交换后
    int M = (L + R) >> 1;
    ls[x] = merge(ls[x],ls[y],L,M);
    rs[x] = merge(rs[x],rs[y],M+1,R);
    sum[x] = sum[ls[x]] + sum[rs[x]];
    return x;
}

void dfs(int &x){
    x = ++dfn;
    scanf("%lld",&v);
    if(v){
        update(rt[x],1,n);
        return;
    }
    else {
        int Ls,Rs;
        dfs(Ls);dfs(Rs);
        u = v = 0;
        rt[x] = merge(rt[Ls],rt[Rs],1,n);
        ans += min(u,v);
    }
}

int main(){
    freopen("test.in","r",stdin);
    scanf("%d",&n);
    int x;
    dfs(x);
    printf("%lld\n",ans);
    return 0;
}
Last modification:October 3rd, 2019 at 03:17 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment