题目

CF上提交WA on test2

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
struct node2{
	int to,nxt,w;
}edge[N];
int head[N],cnt;
int dep[N];
int dfn[N],cntt,sz[N];
void add(int a,int b,int l){
	edge[++cnt].to=b;
	edge[cnt].w=l;
	edge[cnt].nxt=head[a];
	head[a]=cnt;
}
void dfs(int u,int fa){
	dfn[u]=++cntt;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa){
			continue;
		}
		dep[v]=dep[u]+1;
		dfs(v,u);
		sz[u]=sz[v]+1;
	}
}
struct node4{
	int id,val;
}a[N],j[N],o[N];
int cnt1,cnt2;
struct node{
	int left,right,sum,lazy;
}tree[N];
struct node1{
	int left,right,sum,lazy;
}tree1[N];
void pushup(int x){
	tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
}
void build(int x,int l,int r){
	tree[x].left=l;
	tree[x].right=r;
	if(l==r){
		tree[x].sum=j[l].val;
		return ;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
void pushdown(int x){
	int la=tree[x].lazy;
	if(la!=0){
		tree[x<<1].sum+=la*(tree[x<<1].right-tree[x<<1].left+1);
		tree[x<<1|1].sum+=la*(tree[x<<1|1].right-tree[x<<1|1].left+1);
		tree[x<<1].lazy+=la;
		tree[x<<1|1].lazy+=la;
		tree[x].lazy=0;  
	}
}
void update(int x,int from,int to,int v){
	if(from<=tree[x].left&&to>=tree[x].right){
		tree[x].sum+=v*(tree[x].right-tree[x].left+1);
		tree[x].lazy+=v;
		return ;
	}
	pushdown(x);
	int mid=(tree[x].left+tree[x].right)>>1;
	if(from<=mid){
		update(x<<1,from,to,v);
	}
	if(to>mid){
		update(x<<1|1,from,to,v);
	}
	pushup(x);
}
int query(int x,int l,int r){
	if(l<=tree[x].left&&r>=tree[x].right){
		return tree[x].sum;
	}
	pushdown(x);
	int mid=(tree[x].left+tree[x].right)>>1;
	int ans=0;
	if(l<=mid){
		ans+=query(x<<1,l,r);
	}
	if(r>mid){
		ans+=query(x<<1|1,l,r);
	}
	return ans;
}
void pushup1(int x){
	tree1[x].sum=tree1[x<<1].sum+tree1[x<<1|1].sum;
}
void build1(int x,int l,int r){
	tree1[x].left=l;
	tree1[x].right=r;
	if(l==r){
		tree1[x].sum=o[l].val;
		return ;
	}
	int mid=(l+r)>>1;
	build1(x<<1,l,mid);
	build1(x<<1|1,mid+1,r);
	pushup1(x);
}
void pushdown1(int x){
	int la=tree1[x].lazy;
	if(la!=0){
		tree1[x<<1].sum+=la*(tree1[x<<1].right-tree1[x<<1].left+1);
		tree1[x<<1|1].sum+=la*(tree1[x<<1|1].right-tree1[x<<1|1].left+1);
		tree1[x<<1].lazy+=la;
		tree1[x<<1|1].lazy+=la;
		tree1[x].lazy=0;  
	}
}
void update1(int x,int from,int to,int v){
	if(from<=tree1[x].left&&to>=tree1[x].right){
		tree1[x].sum+=v*(tree1[x].right-tree1[x].left+1);
		tree1[x].lazy+=v;
		return ;
	}
	pushdown1(x);
	int mid=(tree1[x].left+tree1[x].right)>>1;
	if(from<=mid){
		update1(x<<1,from,to,v);
	}
	if(to>mid){
		update1(x<<1|1,from,to,v);
	}
	pushup1(x);
}
int query1(int x,int l,int r){
	if(l<=tree1[x].left&&r>=tree1[x].right){
		return tree1[x].sum;
	}
	pushdown1(x);
	int mid=(tree1[x].left+tree1[x].right)>>1;
	int ans=0;
	if(l<=mid){
		ans+=query1(x<<1,l,r);
	}
	if(r>mid){
		ans+=query1(x<<1|1,l,r);
	}
	return ans;
}
signed main(){
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i].val);
		a[i].id=i;
	}
	for(int i=1;i<=n-1;i++){
		int u,v;
		scanf("%lld%lld",&u,&v);
		add(u,v,1);
		add(v,u,1);
	}
	for(int i=1;i<=n;i++){
		sz[i]=1;
	}
	dfs(1,0);
	for(int i=1;i<=n;i++){
		sz[i]+=1;
//		printf("%d %d\n",sz[i],dep[i]);
		if(dep[i]%2==1){
			++cnt1;
			j[cnt1].val=a[i].val;
			j[cnt1].id=a[i].id;
		}
		else{
			cnt2++;
			o[cnt2].val=a[i].val;
			o[cnt2].id=a[i].id;
		}
	}
//	printf("*\n");
	build(1,1,cnt1);
	build1(1,1,cnt2);
	for(int i=1;i<=m;i++){
		int opt,u;
		scanf("%lld%lld",&opt,&u);
		if(opt==1){
			int v;
			scanf("%lld",&v);
			int l=0,r=cnt2;
			while(l<r){
				int mid=(l+r)>>1;
				if(o[mid].id<u){
					l=mid+1;
				}
				else{
					r=mid;
				}
			}
			int x=l;
			l=0,r=cnt2;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(o[mid].id>u+sz[u]-1){
					r=mid-1;
				}
				else{
					l=mid;
				}
			}
			int y=l;
			cout<<x<<" "<<y<<endl;
			if(dep[u]%2==0){
				update1(1,x,y,v);
			}
			else{
				update1(1,x,y,-v);
			}
			l=0,r=cnt1;
			while(l<r){
				int mid=(l+r)>>1;
				if(j[mid].id<u){
					l=mid+1;
				}
				else{
					r=mid;
				}
			}
			x=l;
			l=0,r=cnt1;
			while(l<r){
				int mid=(l+r+1)>>1;
				if(j[mid].id>u+sz[u]-1){
					r=mid-1;
				}
				else{
					l=mid;
				}
			}
			y=l;
//			cout<<x<<" "<<y<<endl;
			if(dep[u]%2==0){
				update(1,x,y,-v);
			}
			else{
				update(1,x,y,v);
			}
		}
		else{
//			if(n==10&&m==10&&u==4){
//				printf("768\n");
//				continue;
//			}
			if(dep[u]%2==0){
				int l=0,r=cnt2;
				while(l<r){
					int mid=(l+r)>>1;
					if(o[mid].id<u){
						l=mid+1;
					}
					else{
						r=mid;
					}
				}
				printf("%lld\n",query1(1,l,l));
			}
			else{
				int l=0,r=cnt1;
				while(l<r){
					int mid=(l+r)>>1;
					if(j[mid].id<u){
						l=mid+1;
					}
					else{
						r=mid;
					}
				}
				printf("%lld\n",query(1,l,l));
			}
		}
	}
	return 0;
}