首页 > 代码库 > BZOJ 2212 [Poi2011]Tree Rotations（线段树合并）
BZOJ 2212 [Poi2011]Tree Rotations（线段树合并）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2212
【题目大意】
给出一棵二叉树，每个叶节点上有一个权值，现在可以任意交换左右儿子，
使得逆序对最少，求最少的逆序对数量
【题解】
我们发现对于每个非叶节点来说，其贡献值为左右两个儿子的权值树上，
每个节点想反位置的数量和乘积，比如左儿子的权值树左节点和右儿子权值树的右节点相乘，
那么我们对于每个节点建立一颗权值线段树，仅保留非0链，
递归合并这些权值线段树，同时每次将相反位置数量乘积的最小值累加到答案即可
【代码】
#include <cstdio>#include <algorithm>#include <cstring>#include <vector>using namespace std;const int N=400010,M=N*20;typedef long long LL;int n,a[N],cnt,Root,root[N];int Tree[N][2];LL Ans,Ans0,Ans1;void Read_Tree(int &x){ x=++cnt; scanf("%d",&a[x]); if(a[x])return; Read_Tree(Tree[x][0]); Read_Tree(Tree[x][1]);}namespace Segment_Tree{ int tot; struct node{int l,r,a,b,sum;}T[M]; void up(int x){T[x].sum=T[T[x].l].sum+T[T[x].r].sum;} int build(int l,int r,int p){ int x=++tot; T[x].a=l; T[x].b=r; T[x].sum=0; if(l==r){T[x].sum=1;return x;} int mid=(l+r)>>1; if(p<=mid){T[x].l=build(l,mid,p);} else{T[x].r=build(mid+1,r,p);} return up(x),x; } int merge(int x,int y){ if(!x||!y)return x^y; Ans0+=(LL)T[T[x].r].sum*(LL)T[T[y].l].sum; Ans1+=(LL)T[T[x].l].sum*(LL)T[T[y].r].sum; T[x].l=merge(T[x].l,T[y].l); T[x].r=merge(T[x].r,T[y].r); return up(x),x; } void dfs(int x){ if(a[x])return; dfs(Tree[x][0]); dfs(Tree[x][1]); Ans0=Ans1=0; root[x]=merge(root[Tree[x][0]],root[Tree[x][1]]); Ans+=min(Ans0,Ans1); }}int main(){ scanf("%d",&n); Read_Tree(Root); for(int i=1;i<=cnt;i++)if(a[i]!=0)root[i]=Segment_Tree::build(1,n,a[i]); Segment_Tree::dfs(Root); printf("%lld\n",Ans); return 0;}BZOJ 2212 [Poi2011]Tree Rotations（线段树合并）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。