求条
查看原帖
求条
983555
fengzhaoyu楼主2025/1/12 16:52

样例都错了

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int cow[N],a[N],rt[N],ans[N];
struct node{
	int ls,rs;
	int sum;
}t[N*80];
int aa;
int n,cnt,len,mx;
vector<int>g[N];
int read()
{
	int t=1,x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')t=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return t*x;
}
void push_up(int u)
{
	int ls=t[u].ls,rs=t[u].rs;
	t[u].sum=t[ls].sum+t[rs].sum;
}
void chang(int &u,int l,int r,int x)
{
	if(!u) u=++cnt;
	if(l==r)
	{
		t[u].sum++;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) chang(t[u].ls,l,mid,x);
	else chang(t[u].rs,mid+1,r,x);
	push_up(u);
}
int kth(int u,int l,int r,int x,int y)
{
	if(x<=l && y>=r)
	{
		return t[u].sum;
	}
	int mid=l+r>>1;
	int s=0;
	if(x<=mid) s+=kth(t[u].ls,l,mid,x,y);
	if(y>mid) s+=kth(t[u].rs,mid+1,r,x,y);
	return s;
}
int merge(int p,int q,int l,int r)
{
	if(!q||!p) return p+q;
	if(l==r)
	{
		t[p].sum+=t[q].sum;
		return p;
	}
	int mid=l+r>>1;
	t[p].ls=merge(t[p].ls,t[q].ls,l,mid);
	t[p].rs=merge(t[p].rs,t[q].rs,mid+1,r);
	push_up(p);
	return p;
}
void dfs(int now,int fa)
{
	for(auto tmp:g[now])
	{
		if(tmp!=fa)
		{
			dfs(tmp,now);
			rt[now]=merge(rt[now],rt[tmp],1,mx);
		}
	}
	ans[now]=kth(rt[now],1,mx,aa+1,mx);
}
signed main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		cow[i]=read();
		a[i]=cow[i];
		
	}
	sort(a+1,a+1+n);
	len=unique(a+1,a+1+n)-a-1;
	mx=len;
	for(int i=1;i<=n;i++)
	{
		aa=lower_bound(a+1,a+1+len,cow[i])-a;
		chang(rt[i],1,mx,aa);
	}
	for(int i=2;i<=n;i++)
	{
		int u=read();
		g[u].push_back(i);
		g[i].push_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		printf("%lld\n",ans[i]);
	}
	return 0;
}
2025/1/12 16:52
加载中...