洛谷3605 Promotion Counting

线段树合并都是蓝题了嘛我可能和时代脱轨了emm...

直接离散化然后合并就好啦w

生病了真难受QAQ

//Love and Freedom.

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define ll long long

#define inf 20021225

#define mxn 100010

using namespace std;

struct node

{

	int ls,rs,sum;

}t[mxn*40];

int cnt,rt[mxn],ans[mxn];

struct edge

{

	int to,lt;

}e[mxn];

int val[mxn],in[mxn],ecnt;

int p[mxn],dd[mxn],n;

void add(int x,int y)

{

	e[++ecnt].to=y;e[ecnt].lt=in[x];in[x]=ecnt;

}

void pushup(int x)

{

	t[x].sum = t[t[x].ls].sum+t[t[x].rs].sum;

}

int merge(int x,int y,int l,int r)

{

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

	if(l==r)

	{

		t[x].sum+=t[y].sum;

		return x;

	}

	int mid = (l+r)>>1;

	t[x].ls=merge(t[x].ls,t[y].ls,l,mid);

	t[x].rs=merge(t[x].rs,t[y].rs,mid+1,r);

	pushup(x);	return x;

}

void insert(int &x,int l,int r,int d)

{

	if(!x)	x=++cnt; t[x].sum++;

	if(l==r)	return;

	int mid=(l+r)>>1;

	if(d<=mid)	insert(t[x].ls,l,mid,d);

	else	insert(t[x].rs,mid+1,r,d);

	pushup(x);

}

int query(int x,int l,int r,int d)

{

	if(!x)	return 0;

	if(l==r)	return t[x].sum;

	int mid=(l+r)>>1;

	if(d<=mid)	return query(t[x].ls,l,mid,d)+t[t[x].rs].sum;

	else	return query(t[x].rs,mid+1,r,d);

}

bool cmp(int x,int y)

{

	return val[x]<val[y];

}

void dfs(int x)

{

	for(int i=in[x];i;i=e[i].lt)

		dfs(e[i].to);

	insert(rt[x],1,n+1,p[x]);// int tmp = ;

	for(int i=in[x];i;i=e[i].lt)

		rt[x]=merge(rt[x],rt[e[i].to],1,n+1);

	ans[x] = query(rt[x],1,n+1,p[x]+1);

}

int main()

{

	int f;

	scanf("%d",&n);

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

		scanf("%d",&val[i]),dd[i]=i;

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

	for(int i=1;i<=n;i++)	p[dd[i]]=i;

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

	{

		scanf("%d",&f);

		add(f,i);

	}

	dfs(1);

	for(int i=1;i<=n;i++)	printf("%d\n",ans[i]);

	return 0;

}

巴特西

洛谷3605 Promotion Counting

最新文章

热门文章