通过观察与思考,我们可以发现,交换一个结点的两棵子树,只对这两棵子树内的节点的逆序对个数有影响,对这两棵子树以外的节点是没有影响的。嗯,然后呢?(っ•̀ω•́)っ
然后,我们就可以对于每一个节点的两棵子树,求出其交换前与交换后的两棵子树内的逆序对个数,取最小就好啦!
怎么求啊,不能暴力吧,TLE啊,不会了呀!!! (ノ`⊿´)ノ(掀桌
对了,我们有线段树合并!(o゚▽゚)o
(如果不知道线段树合并是什么可以看这一篇文章哦。)
对于每一个叶节点,我们都可以建一棵权值线段树,然后一步一步合并上来,顺便求出两颗子树交换前和交换后的次数就好了。
一次线段树合并的时间复杂度就是两棵线段树之间重复节点的个数,由于这道题目的特殊性,所以两棵线段树之间重复节点的个数不会太多,总的时间复杂度就是O(nlogn)左右啦!(゚▽゚*)
代码:
#include<iostream> #include<cstdio> using namespace std; //val存储每个节点的值,ls存储每个节点的左儿子编号 ,rs存储每个节点的右儿子编号 int n=0,tot=0,t=0,val[8000000],ls[8000000],rs[8000000]; long long ans=0,anon=0,antw=0; int builnetre(int l,int r,int x)//建一棵新的线段树 { val[++tot]=1; if(l==r) return tot; int mid=(l+r)>>1,nw=tot; if(x<=mid) ls[nw]=builnetre(l,mid,x); else rs[nw]=builnetre(mid+1,r,x); return nw; } int mergtwtre(int l,int r,int x,int y)//合并两棵线段树 { if(!x||!y) return (!x)?y:x; if(l==r) { val[++tot]=val[x]+val[y]; return tot; } int mid=(l+r)>>1,nw=++tot; anon+=(long long)(val[rs[x]])*val[ls[y]];//anon为不交换的逆序对个数 antw+=(long long)(val[rs[y]])*val[ls[x]];//antw为交换后的逆序对个数 ls[nw]=mergtwtre(l,mid,ls[x],ls[y]); rs[nw]=mergtwtre(mid+1,r,rs[x],rs[y]); val[nw]=val[ls[nw]]+val[rs[nw]]; return nw; } int worea() { scanf("%d",&t); if(t) return builnetre(1,n,t); int nw=mergtwtre(1,n,worea(),worea()); ans+=min(anon,antw);//取最小累加 anon=antw=0;//注意:这个赋值语句不能放在合并函数之前,不然它们的值就会在下一层的合并中改变,就无法达到初始化的效果了 return nw; } int main() { scanf("%d",&n); worea(); printf("%lld",ans); return 0; }
参考文章。