bzoj 4756: [Usaco2017 Jan]Promotion Counting【dfs+树状数组】

思路还是挺好玩的

首先简单粗暴的想法是dfs然后用离散化权值树状数组维护，但是这样有个问题就是这个全局的权值树状数组里并不一定都是当前点子树里的

第一反应是改树状数组，但是显然不太现实，但是可以这样想，就是现在统计子树之前把查到的答案减去，然后再查子树最后加上查到的答案，这样相当于去重了

方便起见，离散化的时候按从大到小的顺序，这样就变成了求比当前点小的点

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

const int N=100005;

int n,a[N],g[N],h[N],cnt,c[N],ans[N];

map<int,int>mp;

struct qwe

{

	int ne,to;

}e[N<<1];

bool cmp(const int &a,const int &b)

{

	return a>b;

}

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

void ins(int x)

{

	for(int i=x;i<=n;i+=(i&(-i)))

		c[i]++;

}

int ques(int x)

{

	int r=0;

	for(int i=x;i>=1;i-=(i&(-i)))

		r+=c[i];

	return r;

}

void dfs(int u)

{

	ans[u]-=ques(a[u]);

	for(int i=h[u];i;i=e[i].ne)

		dfs(e[i].to);

	ans[u]+=ques(a[u]);

	ins(a[u]);

}

int main()

{

	n=read();

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

		a[i]=g[i]=read();

	for(int i=2;i<=n;i++)

	{

		int x=read();

		add(x,i);

	}

	sort(g+1,g+1+n,cmp);

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

		mp[g[i]]=i;

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

		a[i]=mp[a[i]];

	dfs(1);

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

		printf("%d\n",ans[i]);

	return 0;

}

巴特西

bzoj 4756: [Usaco2017 Jan]Promotion Counting【dfs+树状数组】

最新文章

热门文章