BZOJ2212&3702: [Poi2011]Tree Rotations

题目大意：给定一颗完全二叉树，每个叶子节点有一个权值，你可以任意交换每个点的左右儿子，使得最后整棵树中序遍历的逆序对个数最少 交换左右儿子不会影响左右儿子子树中的逆序对个数，只会影响这两颗子树之间的逆序对个数，而左右儿子子树中是否交换左右儿子不会影响这两颗字数之间的逆序对个数，所以我们可以对每个结点的子树分开考虑，所有节点的两个子树间的逆序对个数总和就是整个树的逆序对个数总和 然后对于每个节点，我们就选择两种方式中逆序对个数小的方式，这一步可以用线段树合并（或者splay启发式合并）来在O(NlogN)的时间复杂度内计算出来答案 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define N 4000010 using namespace std; long long a[N],cnt; long long ch[N][2]; long long rt[N],cn,CH[N][2],sum[N],CNT; long long n; void addnew(long long &x,long long l,long long r,long long v) { CNT++;x=CNT; sum[x]++; if(l==r) return; long long mid=(l+r)>>1; if(v<=mid) addnew(ch[x][0],l,mid,v); else addnew(ch[x][1],mid+1,r,v); } void build(long long &x) { cnt++;x=cnt; scanf("%lld",&a[x]); if(a[x]!=0) { addnew(rt[x],1,n,a[x]); return; } build(CH[x][0]); build(CH[x][1]); } long long ans,ANS; long long merge(long long x,long long y) { if(!x) return y; if(!y) return x; ans+=sum[ch[x][0]]*sum[ch[y][1]]; ch[x][0]=merge(ch[x][0],ch[y][0]); ch[x][1]=merge(ch[x][1],ch[y][1]); sum[x]=sum[ch[x][0]]+sum[ch[x][1]]; return x; } void dfs(long long x) { long long lc=CH[x][0],rc=CH[x][1]; if(a[x]) return; dfs(lc);dfs(rc); long long tot=sum[rt[lc]]*sum[rt[rc]]; ans=0; rt[x]=merge(rt[lc],rt[rc]); ANS+=min(ans,tot-ans); } int main() { scanf("%lld",&n); long long root; build(root); dfs(root); printf("%lld",ANS); }