BZOJ4034 [HAOI2015]T2 【DFS序+线段树】

tonyfang posted @ 2016年9月04日 21:20 in BZOJ with tags c++ OI , 1508 阅读

题目大意:有一棵$n$个点的树,$q$次操作,每个点有点权,1号点为根。

1. 修改点权。

2. 修改子树内所有点的点权。

3. 询问点到根路径点权和。

*4. 修改一个点到根路径上的点点权和。

*5. 询问子树内的点权。

$n \leq 100000, q \leq 100000$

【题解】

记录DFS序,记录进栈以及出栈,进栈为正,出栈为负。

维护线段树。

 

1. 修改点权:单点修改

2. 修改子树内所有点的点权:区间修改

3. 询问点到根路径点权和:区间查询

*4. 修改一个点到根路径上的点点权和:区间修改

*5. 询问子树内的点权:区间查询正值(线段树多维护一个正值和)

本题只涉及前3个操作。本题也可以用树链剖分解决。

 

# include <stdio.h>
using namespace std;

int n, m, val[100010];
const int root = 1;

int head[100010], to[200010], next[200010], tot=0;
int seq[600010], sn=0, in[100010], out[100010];
bool io[600010];

inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void dfs(int x, int fa) {
	++sn;
	in[x] = sn; seq[sn] = val[x];
	io[sn] = 1;
	for (int i=head[x]; i; i=next[i]) {
		if(to[i] == fa) continue;
		dfs(to[i], x);
	}
	++sn;
	out[x] = sn; seq[sn] = -val[x];
	io[sn] = 0;
}

typedef long long ll;
int lc[2400010], rc[2400010];
ll w[2400010], lazy[2400010];
int flag[2400010];

inline void pushdown(int x) {
	if(!lazy[x]) return;
	w[x<<1] += lazy[x] * flag[x<<1];
	w[x<<1|1] += lazy[x] * flag[x<<1|1];
	lazy[x<<1] += lazy[x];
	lazy[x<<1|1] += lazy[x];
	lazy[x] = 0;
}

inline void build(int x, int l, int r) {
	lc[x] = l, rc[x] = r; w[x] = lazy[x] = 0;
	if(l == r) {
		w[x] = (ll)seq[l];
		if(io[l]) flag[x] = 1;
		else flag[x] = -1;
		return ;
	}
	int mid = l+r>>1;
	build(x<<1, l, mid);
	build(x<<1|1, mid+1, r);
	w[x] = w[x<<1] + w[x<<1|1];
	flag[x] = flag[x<<1] + flag[x<<1|1];
}

inline void change(int x, int L, int R, ll delta) {
	int l = lc[x], r = rc[x];
	if(L <= l && r <= R) {
		w[x] = w[x] + flag[x] * delta;
		lazy[x] += delta;
		return ;
	}
	pushdown(x);
	int mid = l+r >> 1;
	if(L > mid) change(x<<1|1, L, R, delta);
	else if(R <= mid) change(x<<1, L, R, delta);
	else {
		change(x<<1, L, mid, delta);
		change(x<<1|1, mid+1, R, delta);
	}
	w[x] = w[x<<1] + w[x<<1|1];
}

inline ll query(int x, int L, int R) {
	int l = lc[x], r = rc[x];
	if(L <= l && r <= R) return w[x];
	pushdown(x);
	int mid = l+r >> 1;
	if(L > mid) return query(x<<1|1, L, R);
	else if(R <= mid) return query(x<<1, L, R);
	else return query(x<<1, L, mid) + query(x<<1|1, mid+1, R);
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i) scanf("%d", &val[i]);
	for (int i=1, u, v; i<n; ++i) {
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(root, 0);
	//for (int i=1; i<=sn; ++i) printf("%d ", seq[i]);
	//printf("\n");
	//for (int i=1; i<=n; ++i) printf("%d ", in[i]);
	//printf("\n");
	//for (int i=1; i<=n; ++i) printf("%d ", out[i]);
	//printf("\n");
	build(1, 1, sn);
	for (int i=1; i<=m; ++i) {
		int opt;
		scanf("%d", &opt);
		if(opt == 1) {
			int x, del;
			scanf("%d%d", &x, &del);
			change(1, in[x], in[x], (ll)del);
			change(1, out[x], out[x], (ll)del);
		}
		else if(opt == 2) {
			int x, del;
			scanf("%d%d", &x, &del);
			change(1, in[x], out[x], (ll)del);
		}
		else if(opt == 3) {
			int x;
			scanf("%d", &x);
			printf("%lld\n", query(1, 1, in[x]));
		}
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter