返回首页

【POI2011】ROT-Tree Rotations 题解

我是题目链接

题解

·这题要用到权值线段树

·为了方便表述，下面记sum[l,r]为某个结点的子树中的，所有权值在[l,r]中的叶结点有几个

·容易推出，对于一个非叶子结点，它两子树之间的逆序对的个数=lson->sum[mid+1,r]*rson->sum[l,mid]

·如果对它进行翻转，那么它两子树之间的逆序对个数=原lson->sum[l,mid]*原rson->sum[mid+1,r]

·上述两式的min值就是它两子树之间的逆序对个数最小值

·为了计算sum[l,r]，我们需要对每个结点开一棵权值线段树，动态开点

·而对左右儿子进行翻转，不影响它两子树之间的逆序对个数

·因此，一个结点子树中的所有逆序对个数=左儿子的两子树之间的逆序对个数+右儿子的两子树之间的逆序对个数+两子树之间的逆序对个数

·上面提到的式子都需要递归求解，复杂度O(n log² n)

·每求解完一个结点的左右子树，就要把它的两个子树的权值线段树合并，以求解当前结点

·合并就随便合吧，反正权值线段树都一样大，谁合给谁都一样

·细节参考代码

#include<bits/stdc++.h>
#define newnode(x) x=new Node,x->lson=x->rson=null
using namespace std;

typedef long long LL;
struct Node
{
	Node *lson,*rson;
	LL sum;
	Node(){lson=rson=NULL;sum=0;}
};
Node *root[400010],*null;
int dfn=0,a[400010];
int ls[400010],rs[400010];
LL sl,sr;

int dfs()
{
	int p=++dfn;
	scanf("%d",a+p);
	if(a[p]) return p;
	ls[p]=dfs();
	rs[p]=dfs();
	return p;
}

void maintain(Node *o){o->sum=o->lson->sum+o->rson->sum;}

void insert(Node* &o,int l,int r,int x)
{
	newnode(o);
	if(l==r){o->sum=1;return;}
	int mid=(l+r)/2;
	if(x<=mid) insert(o->lson,l,mid,x);
	else insert(o->rson,mid+1,r,x);
	maintain(o);
}

Node *merge(Node *x,Node *y)
{
	if(x==null) return y;
	if(y==null) return x;
	sl+=x->lson->sum*y->rson->sum;
	sr+=x->rson->sum*y->lson->sum;
	x->lson=merge(x->lson,y->lson);
	x->rson=merge(x->rson,y->rson);
	maintain(x);
	return x;
}

LL solve(int x)
{
	if(a[x]) return 0;
	LL ans=solve(ls[x])+solve(rs[x]);
	sl=sr=0;
	root[x]=merge(root[ls[x]],root[rs[x]]);
	return ans+min(sl,sr);
}

int main()
{
	int n,rt;
	null=new Node;
	null->lson=null->rson=null;
	cin>>n;
	rt=dfs();
	for(int i=1;i<=dfn;i++)
		if(a[i]) insert(root[i],1,n,a[i]);
	printf("%lld\n",solve(rt));
	return 0;
}