题解 P3521 【[POI2011]ROT-Tree Rotations】

正如前面大佬们所说的： **权值线段树**和**线段树合并**。 对于任意一个节点，交换左右子树对当前节点和前面的所有节点**没有影响**。 因为这是**前序遍历**：根节点->左子树->右子树。可以看到，交换左右子树**对前面的节点无影响**。 我们要求的是逆序对最小，对于一个节点，逆序对有三种： + 在左子树中。 + 在右子树中。 + 跨越了左右子树。 我们清楚，交换子树只会对**第三种情况**产生影响。因此，我们只需要在**合并线段树**的过程中统计交换子树的逆序对个数u和不交换子树的逆序对个数v，取 **min(u,v)** 累加到答案中就行了。 现在的问题是如何找**第三种情况下的逆序对**。 上图：  用p表示左子树，q表示右子树。ls表示左子节点，rs表示右子节点。 很明显，对于除了**叶节点**的每一个节点： 1. 如果不交换： $u+=[p.rs].size*[q.ls].size$ 。 2. 如果交换： $v+=[p.ls].size*[q.rs].size$。 重点：每一次合并线段树时，递归到除了叶节点的所有节点，都要累加逆序对个数**u,v**。 看图模拟一边很容易就明白了。 比如，递归到[1~4]这个节点时，累加u:我们只累加了3、4对1、2行成的 $2*2=4$ 组逆序对。但是继续向下递归到[3~4]时，4对3还有一组逆序对。 **因此，递归到除了叶节点的所有节点时，都要进行累加 u,v 的操作**。 讲完了。 ### 补充------空间复杂度： 我们对每个叶节点都需要进行建树操作，该建树操作的值域是 $[1,n]$ ，而我们每次建树都得到一条链，这条链的长度就是 $logn$ ，因为有 $logn$ 层。 考虑极限情况，有大约 n 个叶节点，那么总的空间就是 $nlogn$ 。 注意： **线段树合并不需要新开节点**。 ### 通俗易懂的代码： ```cpp #include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e5+5; int n,top;//top：创建节点个数 ll ans,u,v;//u,v：逆序对个数 struct Tree{ int ls,rs,size; }da[22*N];//N*logN的空间 int in(){//快读 int x=0;char ch=getchar(); while(ch>'9'||ch<'0') ch=getchar(); while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } int update(int l,int r,int val){//创建权值线段树 int pos=++top; da[pos].size++; if(l==r) return pos; int mid=(l+r)>>1; if(val<=mid) da[pos].ls=update(l,mid,val); else da[pos].rs=update(mid+1,r,val); return pos; } int merge(int p,int q,int l,int r){//合并线段树 if(!q||!p) return (!p)?q:p;//如果有节点为空，返回另一个节点 if(l==r){ da[p].size+=da[q].size; return p; }//叶节点，合并，返回 u+=(ll)da[da[p].rs].size*da[da[q].ls].size;//交换前 v+=(ll)da[da[p].ls].size*da[da[q].rs].size;//交换后 int mid=(l+r)>>1; da[p].ls=merge(da[p].ls,da[q].ls,l,mid);//继续合并左子节点 da[p].rs=merge(da[p].rs,da[q].rs,mid+1,r);//右子节点 da[p].size=da[da[p].ls].size+da[da[p].rs].size;//重置更新当前节点 return p; } int dfs(){ int pos,val=in(); if(val==0){//不是叶节点 int ls=dfs(),rs=dfs();//ls:左子树的权值线段树的根节点，rs同理 u=0;v=0;//记得每次清零 pos=merge(ls,rs,1,n);//pos：合并后的权值线段树的根节点 ans+=min(u,v);//累加答案 } else pos=update(1,n,val);//叶节点，建树 return pos;//返回这颗权值线段树的根节点 } int main(){ n=in(); dfs(); printf("%lld",ans); return 0; } ```