样例过了,数据点一都没办法读入,求助
查看原帖
样例过了,数据点一都没办法读入,求助
214728
剑雪清寒楼主2022/4/25 20:39

第一个数据点都没办法完全读入,看不出来哪里写挂了,有没有dalao帮忙看看( 下面是代码

#include <bits/stdc++.h>
using namespace std;
inline int read() {
	int x,f;char ch;
	for(f=0;!isdigit(ch=getchar());f=ch=='-');
	for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
	return f?-x:x;
}
int rs;
struct edge {
	int to;edge* gone;
}rd[200001];
edge *head[100001];
struct node {
	long long value;
	int dfn,top,dad,wson,size,deep;
}nd[100001];
int cnt,pre[100001];
int n=read();
inline void dfs1(int x,int dep) {
	nd[x].deep=dep;nd[x].size=1;
	for(edge *i=head[x];i!=NULL;i=i->gone) {
		int nex=i->to;
		if(nd[nex].deep) continue;
		nd[nex].dad=x;
		dfs1(nex,dep+1);
		nd[x].size+=nd[nex].size;
		if(nd[nex].size>nd[nd[x].wson].size) nd[x].wson=nex;
	}
	return ;
}
inline void dfs2(int x,int tp) {
	nd[x].top=tp;nd[x].dfn=++cnt;
	if(nd[x].wson) dfs2(nd[x].wson,tp);
	for(edge *i=head[x];i!=NULL;i=i->gone) {
		int nex=i->to;
		if(nd[nex].deep<nd[x].deep || nex==nd[x].wson) continue;
		dfs2(nex,nex);
	}
	return ;
}
struct litree {
	int sum[200001],lazy[200001];
	int ss,lson[200001],rson[200001];
	inline void pushup(int x) { sum[x]=(sum[lson[x]]+sum[rson[x]]); }
	inline void lazy_add(int x,int l,int r) {
		if(lazy[x]==1) {
			int mid=(l+r)>>1;
			sum[lson[x]]=mid-l+1;
			sum[rson[x]]=r-mid;
			lazy[lson[x]]=1;
			lazy[rson[x]]=1;
			lazy[x]=0;
		}else {
			sum[lson[x]]=0;
			sum[rson[x]]=0;
			lazy[lson[x]]=-1;
			lazy[rson[x]]=-1;
			lazy[x]=0;
		}
		return ;
	}
	inline void build (int x,int l,int r) {
		ss++;
		if(l==r) {
			sum[x]=0;
			return ;
		}
		int mid=(l+r)>>1;
		lson[x]=ss+1;
		build(ss+1,l,mid);
		rson[x]=ss+1;
		build(ss+1,mid+1,r);
		pushup(x);
		return ;
	}
	inline void add(int x,int l,int r,int L,int R,int z) {
		if(l>R || r<L) return ;
		if(l>=L && r<=R) {
			if(z==1) sum[x]=r-l+1;
			else sum[x]=0;
			lazy[x]=z;
			return ;
		}
		if(lazy[x]) lazy_add(x,l,r);
		int mid=(l+r)>>1;
		add(lson[x],l,mid,L,R,z);
		add(rson[x],mid+1,r,L,R,z);
		pushup(x);
		return ;
	}
	inline int check(int x,int l,int r,int L,int R) {
		if(l>R || r<L) return 0;
		if(l>=L && r<=R) {
			return sum[x];
		}
		if(lazy[x]) lazy_add(x,l,r);
		int mid=(l+r)>>1;
		int k=(check(lson[x],l,mid,L,R)+check(rson[x],mid+1,r,L,R));
		pushup(x);
		return k;
	}
}tree;
inline void ins(int x) {
	int sum=0,al=0;
	while(nd[x].top!=1) {
		al+=nd[x].dfn-nd[nd[x].top].dfn+1;
		sum+=tree.check(1,1,n,nd[nd[x].top].dfn,nd[x].dfn);
		tree.add(1,1,n,nd[nd[x].top].dfn,nd[x].dfn,1);
		x=nd[nd[x].top].dad;
	}
	al+=nd[x].dfn-nd[nd[x].top].dfn+1;
	sum+=tree.check(1,1,n,nd[nd[x].top].dfn,nd[x].dfn);
	tree.add(1,1,n,nd[nd[x].top].dfn,nd[x].dfn,1);
	printf("%d\n",al-sum);
}
inline void uni(int x) {
	int sum=0;
	sum=tree.check(1,1,n,nd[x].dfn,nd[x].dfn+nd[x].size-1);
	tree.add(1,1,n,nd[x].dfn,nd[x].dfn+nd[x].size-1,-1);
	printf("%d\n",sum);
}
int main() {
	for(int i=2;i<=n;i++) {
		int x=read()+1;
		rd[rs].to=i;rd[rs].gone=head[x];
		head[x]=&rd[rs++];
	}
	dfs1(1,1);
	dfs2(1,1);
	tree.build(1,1,n);
	int q=read();
	for(int i=1;i<=q;i++) {
		char k=getchar();int x=read()+1;
		if(k=='i') {
			ins(x);
		}else {
			uni(x);
		}
	}
	return 0;
}

2022/4/25 20:39
加载中...