请求大佬帮调10pts
查看原帖
请求大佬帮调10pts
701202
high_sky楼主2024/10/14 08:37

虽然说 LG 显示的是 WA,但是下载之后再本地测应该是 RE,大佬帮忙调下,谢谢!!!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <vector>
#define N 100005
#define M 1000000009
#define ls tr[x].lson
#define rs tr[x].rson
#define int long long
using namespace std;
int n,p[N],cnt,rt[N];
vector<int> g[N];
struct node{
	int lson,rson;
	int sum;
}tr[N << 6];
void pushup(int x){
	tr[x].sum = tr[ls].sum + tr[rs].sum;
}
void update(int &x,int l,int r,int pos,int val) {
	if (!x) x = ++cnt;
	if (l == r) {
		tr[x].sum = val;
		return;
	}
	int mid = l + r >> 1;
	if (pos <= mid) update(tr[x].lson,l,mid,pos,val);
	else update(tr[x].rson,mid + 1,r,pos,val);
	pushup(x); 
}
int merge(int a,int b,int l,int r) {
	if (!a || !b) return a + b;
	if (l == r) return tr[a].sum += tr[b].sum,a;
	int mid = l + r >> 1;
	tr[a].lson = merge(tr[a].lson,tr[b].lson,l,mid);
	tr[a].rson = merge(tr[a].rson,tr[b].rson,mid + 1,r);
	pushup(a);
	return a;
}
int query(int x,int l,int r,int L,int R) {
	if (l > R || r < L) return 0;
	if (!x) return 0;
	if (L <= l && r <= R) return tr[x].sum;
	int mid = l + r >> 1;
	return query(ls,l,mid,L,R) + query(rs,mid + 1,r,L,R);
}
void dfs(int cur,int fa) {
	for (auto i : g[cur])
		if (i != fa) {
			dfs(i,cur);
			merge(rt[cur],rt[i],1,1000000000);
		}
}
signed main(){
//	freopen("P3605.in","r",stdin),freopen("P3605.ans","w",stdout);
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> p[i],rt[i] = i,cnt ++;
	for (int i = 1;i <= n;i ++) update(rt[i],1,1000000000,p[i],1);
//	for (int i = 1;i <= n;i ++) cout << tr[rt[i]].sum << ' ';
//	cout << endl;
	for (int i = 2;i <= n;i ++) {
		int x;
		cin >> x;
		g[x].push_back(i);
		g[i].push_back(x);
	}
	dfs(1,0);
	for (int i = 1;i <= n;i ++) {
		if (p[i] + 1 >= 1000000000) puts("0");
		else cout << query(rt[i],1,1000000000,p[i] + 1,1000000000) << endl;
	}
	return 0;
} 
2024/10/14 08:37
加载中...