luogu P3605 [USACO17JAN]Promotion Counting晋升者计数

题目链接

思路

可以说是线段树合并的练手题目吧

也没啥说的，就是dfs，然后合并、、、

看代码吧

错误

和写主席树错的差不多

都是变量写错、、、、

代码

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int maxn=1e5+7;

inline int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int n,tmp,cnt,a[maxn],b[maxn],rt[maxn],ans[maxn],ch[maxn*20][2],siz[maxn*20];

vector<int> t[maxn];

void build(int l,int r,int k,int &now)  {

	now=++cnt;

	siz[now]=1;

	if(l==r)return;

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

	if(k<=mid) build(l,mid,k,ch[now][0]);

	else build(mid+1,r,k,ch[now][1]);

}

int merge(int x,int y) {

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

	siz[x]+=siz[y];

	ch[x][0]=merge(ch[x][0],ch[y][0]);

	ch[x][1]=merge(ch[x][1],ch[y][1]);

	return x;

}

int query(int l,int r,int k,int now) {

	if(r<=k||!now) return 0;

	if(l>k) return siz[now];

	int mid=(l+r)>>1,ans=0;

	ans+=query(l,mid,k,ch[now][0]);

	ans+=query(mid+1,r,k,ch[now][1]);

	return ans;

}

void dfs(int u) {

	for(vector<int>::iterator it=t[u].begin();it!=t[u].end();++it)

		dfs(*it),rt[u]=merge(rt[u],rt[*it]);

	ans[u]=query(1,n,a[u],rt[u]);

}

int main() {

	n=read();

	FOR(i,1,n) a[i]=b[i]=read();

	FOR(i,2,n) tmp=read(),t[tmp].push_back(i);

	sort(b+1,b+1+n);

	tmp=unique(b+1,b+1+n)-b-1;

	FOR(i,1,n) a[i]=lower_bound(b+1,b+1+tmp,a[i])-b,build(1,n,a[i],rt[i]);

	dfs(1);

	FOR(i,1,n) cout<<ans[i]<<"\n";

	return 0;

}