请问这凭什么爆256MB
查看原帖
请问这凭什么爆256MB
308384
Morpheuse楼主2021/12/14 21:43
#include<bits/stdc++.h>
using namespace std;
#define maxn 200001
#define lson p << 1
#define rson p << 1 | 1
struct Tree
{
	int l , r , data , add;
}tr[350000][2];
struct edge
{
	int to , next;
}e[maxn];
int head[maxn],idk;

int opt,u,v,val;
int n,m;
int a[maxn][2],cnt[2],ed[maxn];
short g[maxn];

int bel[maxn][2];
  void add(int x , int y)
{
	e[++ idk].to = y;
	e[idk].next = head[x];
	head[x] = idk;
}
  void pushdown(int p , int s)
{
	if(tr[p][s].add == 0) return;
	tr[lson][s].data += (tr[lson][s].r - tr[lson][s].l + 1) * tr[p][s].add;
	tr[rson][s].data += (tr[rson][s].r - tr[rson][s].l + 1) * tr[p][s].add;
	
	tr[lson][s].add += tr[p][s].add;
	tr[rson][s].add += tr[p][s].add;
	tr[p][s].add = 0;
}
  void build(int l , int r , int p , int s)
{
	if(l == r)
	{
		tr[p][s].l = tr[p][s].r = l;
		tr[p][s].data = a[l][s];
		return;
	}
	int mid = (l + r) >> 1;
	build(l , mid , lson , s);
	build(mid + 1  , r , rson , s);
	tr[p][s].l = tr[lson][s].l , tr[p][s].r = tr[rson][s].r;
	tr[p][s].data = tr[lson][s].data + tr[rson][s].data;
}
  void dfs(int x , int s)
{
	for(int i = head[x] ; i ; i = e[i].next)
	{
		int to = e[i].to , ns = (s ^ 1);
		a[++ cnt[ns]][ns] = g[to];
		bel[to][0] = ns , bel[to][1] = cnt[ns];
		dfs(to , ns);
	}
	ed[x] = cnt[s];
}
  void updata(int l , int r , int p , int val , int s)
{
	if(tr[p][s].r < l || r < tr[p][s].l) return;
	if(l <= tr[p][s].l && tr[p][s].r <= r)
	{
		tr[p][s].data += (tr[p][s].r - tr[p][s].l + 1) * val;
		tr[p][s].add += val;
		return;
	}
	int mid = (tr[p][s].l + tr[p][s].r) >> 1;
	if(l <= mid) updata(l , r , lson , val , s);
	if(mid <= r) updata(l , r , rson , val , s);
}
  int query(int l , int p , int s)
{
	if(l == tr[p][s].l && tr[p][s].r == l) return tr[p][s].data;
	pushdown(p , s);
	int mid = (tr[p][s].l + tr[p][s].r) >> 1;
	if(l <= mid) return query(l , lson , s);
	else return query(l , rson , s);
}

  int read()
{
	int x = 0 , f = 1 ; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-' ? -1 : 1) , c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0' , c = getchar();
	return x * f;
}
int main()
{
	n = read() , m = read();
	for(int i = 1 ; i <= n ; ++ i) g[i] = read();
	
	for(int i = 1 ; i < n ; ++ i)
	{
		u = read() , v = read();
		add(u , v);
	}
	
	bel[1][0] = 0;
	bel[1][1] = 1;
	a[++ cnt[0]][0] = g[1];
	dfs(1 , 0);
	
	build(1 , cnt[0] , 1 , 0);
	build(1 , cnt[1] , 1 , 1);
	
	for(int i = 1 ; i <= m ; ++ i)
	{
		opt = read() , u = read();
		if(opt == 1)
		{
			val = read();
			updata(bel[u][1] , ed[u] , 1 , val , bel[u][0]);
			for(int i = head[u] ; i ; i = e[i].next)
			{
				int to = e[i].to;
				updata(bel[to][1] , ed[to] , 1 , -val , bel[to][0]);
			}
		}
		else printf("%d\n", query(bel[u][1] , 1 , bel[u][0]));
	}
	return 0;
}
2021/12/14 21:43
加载中...