记录编号	439546	评测结果	AAAAAAAAAA
题目名称	Alone	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.844 s
提交时间	2017-08-21 09:46:51	内存使用	46.07 MiB

#include<cstdio>
const int N=1e6+10;
int n,h[N],v[N],fa[N],dfn[N],size[N];
int w[N],head[N],next[N];
void addedge(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
void dfs(int x){
	static int cnt=0;
	dfn[x]=cnt++;
	v[dfn[x]]=h[x];
	size[x]=1;
	for (int i=head[x];i;i=next[i]){
		dfs(w[i]);
		size[x]+=size[w[i]];
	}
}
int Minv[N],Minp[N],tag[N];
#define lc x<<1
#define rc x<<1|1
void update(int x){
	if (Minv[lc]<Minv[rc])
		Minv[x]=Minv[lc],Minp[x]=Minp[lc];
	else
		Minv[x]=Minv[rc],Minp[x]=Minp[rc];
}
void add(int x,int d){
	tag[x]+=d;
	Minv[x]+=d;
}
void pushdown(int x){
	if (tag[x]){
		add(lc,tag[x]);
		add(rc,tag[x]);
		tag[x]=0;
	}
}
void build(int x,int l,int r){
	if (l==r){
		Minv[x]=v[l];
		Minp[x]=l;
		return;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	update(x);
}
void add(int x,int l,int r,int L,int R,int d){
	if (l>=L&&r<=R) return add(x,d);
	pushdown(x);
	int mid=(l+r)>>1;
	if (L<=mid) add(lc,l,mid,L,R,d);
	if (R>mid) add(rc,mid+1,r,L,R,d);
	update(x); 
}
int mv,mp;
void query(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R){
		if (mv>Minv[x]) mv=Minv[x],mp=Minp[x];
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if (L<=mid) query(lc,l,mid,L,R);
	if (R>mid) query(rc,mid+1,r,L,R);
}
struct bit{
	int a[N];
	void add(int p,int d){
		for (;p<=n;p+=p&-p) a[p]+=d;
	}
	int sum(int p){
		int ans=0;
		for (;p;p-=p&-p) ans+=a[p];
		return ans;
	}
	int sum(int l,int r){
		return sum(r)-sum(l-1);
	}
}T;
int main()
{
	freopen("alone.in","r",stdin);
	freopen("alone.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d%d",&h[i],&fa[i]);
		addedge(fa[i],i);
	}
	dfs(0);build(1,1,n);
	for (int i=1;i<=n;i++) T.add(i,1);
	int Q;
	scanf("%d",&Q);
	while (Q--){
		int tp,x,l,r,v;
		scanf("%d%d",&tp,&x);
		l=dfn[x]+1;r=dfn[x]+size[x]-1;
		if (tp==1){
			scanf("%d",&v);
			if (l>r) continue;
			add(1,1,n,l,r,-v);
			while (1){
				mv=1e9;
				query(1,1,n,l,r);
				if (mv<=0) T.add(mp,-1),add(1,1,n,mp,mp,1e9);
					else break;
			}
		}
		else printf("%d\n",T.sum(l,r));
	}
	return 0;
}