BZOJ2212【POI2011】ROT:Tree Rotation 线段树合并

题意：

　　给一棵n(1≤n≤200000个叶子的二叉树，可以交换每个点的左右子树，要求叶子遍历序的逆序对最少。

分析：

　　求逆序对我们可以想到权值线段树，所以我们对每个点建一颗线段树（为了避免空间爆炸，采取动态开点的科技）

　　两个子节点可以交换，于是我们可以递归，自底向上贪心解决问题，每次线段树合并，在合并时，统计交换左右子节点后，横跨当前位置的逆序对数量，以及不交换子节点的情况下的这个数量，将更优的计入答案。这道问题就圆满解决了。

代码：

 #include<bits/stdc++.h>

 #define ll long long

 using namespace std;

 const int N=;

 struct node{ll v;int ls,rs;}t[N*];

 int n,m,tot=,cnt=,nm[N],ls[N],rs[N],rt[N];

 ll ans=,ans1,ans2;

 void read(int x){

     scanf("%d",&nm[x]);

     if(!nm[x]) read(ls[x]=++cnt),

     read(rs[x]=++cnt);return ;

 } void update(int &x,int l,int r,int v){

     if(!x) x=++tot;int mid=l+r>>;

     if(l==r){t[x].v=;return ;}

     if(v<=mid) update(t[x].ls,l,mid,v);

     else update(t[x].rs,mid+,r,v);

     t[x].v=t[t[x].rs].v+t[t[x].ls].v;

 } int merge(int x,int y){

     if(!x||!y) return x|y;

     ans1+=(ll)t[t[x].rs].v*t[t[y].ls].v;

     ans2+=(ll)t[t[x].ls].v*t[t[y].rs].v;

     t[x].ls=merge(t[x].ls,t[y].ls);

     t[x].rs=merge(t[x].rs,t[y].rs);

     t[x].v=t[t[x].ls].v+t[t[x].rs].v;

     return x;

 } void dfs(int x){

     if(!x) return ;

     dfs(ls[x]);dfs(rs[x]);

     if(!nm[x]){

         ans1=ans2=;

         rt[x]=merge(rt[ls[x]],rt[rs[x]]);

         ans+=min(ans1,ans2);

     } return ;

 } int main(){

     scanf("%d",&n);read();

     for(int i=;i<=cnt;i++)

     if(nm[i]) update(rt[i],,n,nm[i]);

     dfs();printf("%lld\n",ans);

     return ;

 }

线段树合并

巴特西

BZOJ2212【POI2011】ROT:Tree Rotation 线段树合并

题意：

分析：

最新文章

热门文章