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<bits/stdc++.h>
#define N 200050
#define LL long long
using 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;
}