P3521 [POI2011]ROT-Tree Rotations [权值线段树合并]

P3521 [POI2011]ROT-Tree Rotations [权值线段树合并]

​​传送门​​

我们发现交换两个子树, 两个子树内部是不会变的, 于是贪心考虑该子树换不换

于是我们建权值线段树, 不换的话逆序对就是左儿子的权值线段树的右儿子 * 右儿子的权值线段树的左儿子, 换了相反

于是我们边统计边合并两颗权值线段树

大致过程 [蒟蒻第一次学权值线段树合并]

代码大概是这样

void Merge(int &x,int y){// 将y合并到x上 if(!x||!y){x = x+y; return;} // 有一个为空就没有必要继续递归了,如果x为空,x继承y就可以了 t[x].val += t[y].val; // 两个子树个数累加 Merge(t[x].ls, t[y].ls); // 递归合并 Merge(t[x].rs, t[y].rs);}

叶子节点(n个)每个插入权值线段树要logn个节点, 所以空间是nlogn的

#include#define N 200050#define LL long longusing namespace std;struct Node{ int ls,rs,val;}t[N*40];LL sum1,sum2,ans;int n,tot;void Modify(int &x,int l,int r,int pos){ if(!x) x = ++tot; t[x].val++; if(l==r) return; int mid = (l+r) >> 1; if(pos<=mid) Modify(t[x].ls,l,mid,pos); else Modify(t[x].rs,mid+1,r,pos);}void Merge(int &x,int y){ if(!x||!y){ x = x+y; return;} t[x].val += t[y].val; sum1 += (LL)t[t[x].rs].val * (LL)t[t[y].ls].val; sum2 += (LL)t[t[x].ls].val * (LL)t[t[y].rs].val; Merge(t[x].ls, t[y].ls); Merge(t[x].rs, t[y].rs);}void Solve(int &pos){ int x; scanf("%d",&x); if(x==0){ int ls=0, rs=0; Solve(ls); Solve(rs); sum1=0, sum2=0; pos = ls; Merge(pos,rs); ans += min(sum1, sum2); } else Modify(pos,1,n,x);}int main(){ scanf("%d",&n); int tmp = 0; Solve(tmp); printf("%lld",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。