Luogu3521 [POI2011]ROT-Tree Rotations(线段树合并)题解

发布于 2021-10-19  38 次阅读


题目大意

给定一颗有 $n$ 个叶节点的二叉树。每个叶节点都有一个权值 $p_i$(注意,根不是叶节点),所有叶节点的权值构成了一个 $1 \sim n$ 的排列。
对于这棵二叉树的任何一个结点,保证其要么是叶节点,要么左右两个孩子都存在。
现在你可以任选一些节点,交换这些节点的左右子树。
在最终的树上,按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 $n$ 的排列,你需要最小化这个排列的逆序对数。

$2 \le n \le 2 \times 10^5$,所有叶节点的权值是一个 $1 \sim n$ 的排列。

解题思路

自己随便玩几个样例,可以发现先序遍历的顺序是根 $\to $左 $\to$ 右,交换一个节点的左右儿子是不会影响前面序列的逆序对的。

发现叶子节点权值不超过 $n$,并且要求逆序对数,那我们考虑权值线段树合并。

我们合并维护叶节点的权值,每次合并儿子节点的两颗线段树时,判断到底是不交换的逆序对数小,还是交换的逆序对数小。

也就是比较 $(tree[tree[x].lson].cnt∗tree[tree[y].rson].cnt)$ (不交换的情况)与 $(tree[tree[x].rson].cnt∗tree[tree[y].lson].cnt)$(交换的情况)。

这里这里 $(tree[tree[x].lson].cnt∗tree[tree[y].rson].cnt)$ 是指左节点在右边值域中的值个数,乘上右节点在左边值域的值个数。交换的话就是右节点在左边值域的个数,乘上左节点在右边值域的个数。

然后显然不能直接每次选小的累加,因为我们统计的是一层的贡献。所以应该是

把交换的放到一个变量 $res1$ 里,不交换的放到一个变量 $res2$ 里,最后整颗线段树合并完了再取个小的值放到 $ans$ 里面。

注意这个题的输入方式有点恶心(也可能是我实现的有点恶心?)。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=400005,LogN=20;

bool St;

struct Node{
    int lson,rson;
    int cnt;
}tree[N*LogN];

int n,L[N],R[N],cnt=0;
int a[N],rt[N],cntNode=0;
long long res1=0,res2=0,ans=0;

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

inline int Read(){
    int x=read();
    a[++cnt]=x;
    int now=cnt;
    if (x==0){
        L[now]=Read();
        R[now]=Read();
    }
    return now;
}

#define lid (tree[id].lson)
#define rid (tree[id].rson)

inline void pushup(int id){
    tree[id].cnt=tree[lid].cnt+tree[rid].cnt;
}

inline void Insert(int& id,int l,int r,int val){
    if (!id) id=++cntNode;
    if (l==r){
        tree[id].cnt=1;
        return void();
    }
    int mid=(l+r)>>1;
    if (val<=mid) Insert(lid,l,mid,val);
    else Insert(rid,mid+1,r,val);
    pushup(id);
}

inline int Merge(int x,int y,int l,int r){
    if (!x) return y;
    if (!y) return x;
    if (l==r){
        tree[x].cnt+=tree[y].cnt;
        return x;
    }
    int mid=(l+r)>>1;
    res1+=1ll*tree[tree[x].lson].cnt*tree[tree[y].rson].cnt;
    res2+=1ll*tree[tree[x].rson].cnt*tree[tree[y].lson].cnt;
    tree[x].lson=Merge(tree[x].lson,tree[y].lson,l,mid);
    tree[x].rson=Merge(tree[x].rson,tree[y].rson,mid+1,r);
    pushup(x);
    return x;
}

inline void dfs(int x,int fath){
    rt[x]=++cntNode;
    if (a[x]) Insert(rt[x],1,n,a[x]);
    if (L[x]>0){ dfs(L[x],x); res1=res2=0; rt[x]=Merge(rt[x],rt[L[x]],1,n); }
    if (R[x]>0){ dfs(R[x],x); res1=res2=0; rt[x]=Merge(rt[x],rt[R[x]],1,n); }
    ans+=min(res1,res2);
}

int main(){
    //freopen("Luogu3521.in","r",stdin);
    //freopen("Luogu3521.out","w",stdout);
    n=read(); Read(); n=cnt;
    // for (int i=1;i<=n;++i)
    //  printf("i=%d a[%d]=%d L[%d]=%d r[%d]=%d\n",i,i,a[i],i,L[i],i,R[i]);
    dfs(1,0);
    printf("%lld\n",ans);
    bool Ed; cerr<<"MemoryUsed:"<<1.0*(&St-&Ed)/1024/1024<<endl;
    return 0;
}

我们无法选择过去,但我们可以改变未来。