线段树合并（【POI2011】ROT-Tree Rotations）

题意

现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有nn个叶子节点，满足这些权值为1…n1…n的一个排列)。可以任意交换每个非叶子节点的左右孩子。

要求进行一系列交换，使得最终所有叶子节点的权值按照前序遍历序写出来，逆序对个数最少。

解法

我们对每一个叶子节点建立一颗权值线段树，然后，我们考虑将两个叶子节点上的线段树合并起来，然后我们考虑逆序对的个数。

如果我们将左儿子的线段树放在前面，则产生的逆序对数为左儿子右边的sum * 右儿子左边的sum，反之同理。然后我们每次合并求出这两个之中的最小值加入ans中就好了。

代码

令我感到神奇的是，如果我们将dfs中的两句判断放在外面，常数为原来的3倍，如果不开O2就会TLE。

~~ 可我明明打的跟别人一样的代码，别人不开O2都只要300ms。自带常数型选手的悲哀。╮(╯﹏╰）╭ ~~

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <cctype>

#define INF 2139062143

#define MAX 0x7ffffffffffffff

#define del(a,b) memset(a,b,sizeof(a))

using namespace std;

typedef long long ll;

template<typename T>

inline void read(T&x)

{

    x=0;T k=1;char c=getchar();

    while(!isdigit(c)){if(c=='-')k=-1;c=getchar();}

    while(isdigit(c)){x=x*10+c-'0';c=getchar();}x*=k;

}

const int maxn=8000000+5;

struct node{

	int lc,rc,sum;

	node(int lc=0,int rc=0,int sum=0):lc(lc),rc(rc),sum(sum){}

}T[maxn*4];

int root[maxn];

int a[maxn];

int sz;

ll ans1,ans2;

void build(int x){

	read(a[x]);

	if(a[x]) return;

	T[x].lc=++sz;build(T[x].lc);

	T[x].rc=++sz;build(T[x].rc);

}

void updata(int l,int r,int pos,int val,int &x){

	if(!x) x=++sz;

	T[x].sum+=val;

	if(l==r) return;

	int mid=(l+r)/2;

	if(pos<=mid) updata(l,mid,pos,val,T[x].lc);

	else updata(mid+1,r,pos,val,T[x].rc);

}

int Merge(int x,int y){

	if(!x||!y) return x+y;

	ans1+=1ll*T[T[x].lc].sum*T[T[y].rc].sum;

	ans2+=1ll*T[T[x].rc].sum*T[T[y].lc].sum;

	T[x].lc=Merge(T[x].lc,T[y].lc);

	T[x].rc=Merge(T[x].rc,T[y].rc);

	T[x].sum=T[T[x].lc].sum+T[T[x].rc].sum;

	return x;

}

ll ans=0;

void dfs(int x){

	//若为叶子结点，往下递归会TLE???

	if(!a[x]){

		if(T[x].lc) dfs(T[x].lc);

		if(T[x].rc) dfs(T[x].rc);

		ans1=0;ans2=0;

		root[x]=Merge(root[T[x].lc],root[T[x].rc]);

		ans+=1ll*min(ans1,ans2);

	}

}

int n;

int main()

{

	read(n);

	build(sz=1);

    for(int i=1;i<=sz;i++)

      if(a[i])

        updata(1,n,a[i],1,root[i]);

    dfs(1);

    printf("%lld\n",ans);

	return 0;

}

巴特西

线段树合并（【POI2011】ROT-Tree Rotations）

线段树合并（【POI2011】ROT-Tree Rotations）

题意

解法

代码

最新文章

热门文章