输入格式真的毒瘤
权值线段树合并。
我们先对每一个叶子建一棵权值线段树,并把它自己的权值插入到里面。
我们不妨设原树中当前节点为 \(u\),爸爸 \(fa\),左儿子 \(lc\),右儿子 \(rc\),那么显然这棵树中的逆序对分为 \(3\) 个部分:\(lc\) 里的逆序对,\(rc\) 里的逆序对和跨 \(lc\) 和 \(rc\) 的逆序对。
而我们现在已经把 \(lc\) 里的逆序对和 \(rc\) 里的逆序对算好了,现在需要求出跨 \(lc\) 和 \(rc\) 的逆序对,也就是合并 \(lc\) 和 \(rc\) 。然后我们发现,无论 \(lc\) 内的子树怎么换来换去,\(rc\)内的子树怎么换来换去,都是对跨 \(lc\) 和 \(rc\) 的逆序对个数没有影响的。
同理,无论我们交不交换 \(lc\) 和 \(rc\),对 \(fa\) 那一层的合并也是没有影响的。
所以对于跨 \(lc\) 和 \(rc\) 的逆序对,我们分交换 \(lc\)、\(rc\) 和不交换的情况算出两种情况的逆序对个数,再取较小值就好了。
我们遍历两棵权值线段树来暴力合并两棵权值线段树。
那么对于 \(lc\) 和 \(rc\) 权值线段树中同一位置的点 \(a\)、\(b\),若不交换 \(lc\) 和 \(rc\),显然 \(lc\) 中的点的编号(这里的编号是指前序遍历的先后顺序)肯定都在 \(rc\) 前,\(a\) 右儿子的权值必定大于 \(b\) 左儿子的权值,所以 \(size[ch[a][1]]*size[ch[b][0]]\) 就是这一位置的答案了。
同理,如果交换 \(lc\) 和 \(rc\),这一位置的答案就是 \(size[ch[a][0]]*size[ch[b][1]]\)。
最后合并完统计答案即可。
代码如下:
#include<bits/stdc++.h>
#define N 200010
#define int long long
using namespace std;
struct Tree
{
int ch[2],size;
}t[N<<5];
int n,tot,ans,num1,num2;
int update(int l,int r,int val)
{
int u=++tot;
t[u].size=1;
if(l==r) return u;
int mid=(l+r)>>1;
if(val<=mid) t[u].ch[0]=update(l,mid,val);
else t[u].ch[1]=update(mid+1,r,val);
return u;
}
int merge(int a,int b,int l,int r)//把b合并至a
{
if(!a||!b) return a+b;
if(l==r)
{
t[a].size+=t[b].size;
return a;
}
num1+=t[t[a].ch[1]].size*t[t[b].ch[0]].size;//不交换的答案
num2+=t[t[b].ch[1]].size*t[t[a].ch[0]].size;//交换后的答案
int mid=(l+r)>>1;
t[a].ch[0]=merge(t[a].ch[0],t[b].ch[0],l,mid);
t[a].ch[1]=merge(t[a].ch[1],t[b].ch[1],mid+1,r);
t[a].size+=t[b].size;
return a;
}
int dfs()
{
int u,val;
scanf("%lld",&val);
if(!val)
{
int lc=dfs(),rc=dfs();
num1=num2=0;
u=merge(lc,rc,1,n);
ans+=min(num1,num2);//ans加上较小值
}
else u=update(1,n,val);
return u;
}
signed main()
{
scanf("%lld",&n);
dfs();
printf("%lld\n",ans);
return 0;
}
标签:XSY2014,ch,lc,权值,POI2011,Tree,rc,size,逆序
From: https://www.cnblogs.com/ez-lcw/p/16837101.html