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

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

题目大意:有一棵$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;
}

 

jio balance check 说:
2022年12月18日 21:02

Reliance Jio is India’s most popular telecom service company. Jio offers many options for checking balance and validity. Jio provided USSD codes for each and every mobile process to make it easy. jio balance check You may check your JIO primary balance information will be shown on your phone’s screen. You can also check your JIO balance, Data Usage.

SBI Net Banking 说:
2023年1月29日 22:03

State Bank of India is one of the largest Indian banking services which is also spread widely across the country and in foreign nations as well. And it is a great decision if you have already opened up your banking account SBI Net Banking with the SBI because you will understand and get more benefits that you can avail of through their online banking service through online and from their Yono app as well to use SBI credit card and debit card services too.

boardmodelpaper.com 说:
2024年1月05日 20:22

Board Model Papers 2024 Download with Suggestions for 10th Class Textbooks 2024 Pdf Download and SSLC New Syllabus Sample Question Paper 2024 and different types of model papers boardmodelpaper.com and question papers for following the website and Arts, Science, Commerce Stream Subject Wise Solved Question Bank for Hindi & English Medium Students with Exam Pattern & Blueprint and subject Wise with 11th & 12th Question Bank 2024 for General & Vocational Course Languages & Subjects Important Question for the above link.


登录 *


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