BZOJ 4034 [HAOI2015]树上操作（树链剖分）

题目链接 BZOJ4034

这道题树链剖分其实就可以了。

单点更新没问题。

相当于更新

[f[x], f[x]]这个区间。

f[x]表示树链剖分之后每个点的新的标号。

区间更新的话类似DFS序，求出所对应的区间。

也就是[f[x], f[x] + size[x] - 1]。

给这个区间加上a即可。

询问的时候有两种方法，一个是直接套模板。

还有一种方法是，因为是查询x到1的权值和，

所以跟着top[x]走就可以了。

第一种方法：

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)    for (int i(a); i <= (b); ++i)

#define dec(i, a, b)    for (int i(a); i >= (b); --i)

#define lson        	i << 1, L, mid

#define rson       	i << 1 | 1, mid + 1, R

typedef long long LL;

const int N = 300010;

LL a[N], sum[N << 2], lazy[N << 2], y;

int f[N], fp[N], son[N], deep[N], father[N], sz[N], top[N];

int x, tot, n, m, op;

vector <int> v[N];

void dfs1(int x, int fa, int dep){

	deep[x] = dep;

	father[x] = fa;

	son[x] = 0;

	sz[x] = 1;

	int ct = (int)v[x].size();

	rep(i, 0, ct - 1){

		int u = v[x][i];

		if (u == fa) continue;

		dfs1(u, x, dep + 1);

		sz[x] += sz[u];

		if (sz[son[x]] < sz[u]) son[x] = u;

	}

}

void dfs2(int x, int tp){

	top[x] = tp;

	f[x] = ++tot;

	fp[f[x]] = x;

	if (son[x]) dfs2(son[x], tp);

	int ct = (int)v[x].size();

	rep(i, 0, ct - 1){

		int u = v[x][i];

		if (u == father[x] || u == son[x]) continue;

		dfs2(u, u);

	}

}

inline void pushup(int i){

	sum[i] = sum[i << 1] + sum[i << 1 | 1];

}

inline void pushdown(int i, int L, int R){

	int mid = (L + R) >> 1;

	lazy[i << 1] += lazy[i];

	sum[i << 1]  += lazy[i] * (mid - L + 1);

	lazy[i << 1 | 1] += lazy[i];

	sum[i << 1 | 1] += lazy[i] * (R - mid);

	lazy[i] = 0;

}

void build(int i, int L, int R){

	if (L == R){ sum[i] = a[fp[L]]; return; }

	int mid = (L + R) >> 1;

	build(lson);

	build(rson);

	pushup(i);

}

void update(int i, int L, int R, int l, int r, LL val){

	if (l == L && R == r){

		sum[i]  += val * (R - L + 1);

		lazy[i] += val;

		return ;

	}

	if (lazy[i]) pushdown(i, L, R);

	int mid = (L + R) >> 1;

	if (r <= mid) update(lson, l, r, val);

	else if (l > mid) update(rson, l, r, val);

	else{

		update(lson, l, mid, val);

		update(rson, mid + 1, r, val);

	}

	pushup(i);

}

LL query_sum(int i, int L, int R, int l, int r){

	pushdown(i, L, R);

	if (L == l && R == r) return sum[i];

	int mid = (L + R) >> 1;

	if (r <= mid) return query_sum(lson, l, r);

	else if (l > mid) return query_sum(rson, l, r);

	else return query_sum(lson, l, mid) + query_sum(rson, mid + 1, r);

}

LL find_sum(int x, int y){

	int f1 = top[x], f2 = top[y];

	LL ret = 0;

	for (; f1 != f2; ){

		if (deep[f1] < deep[f2]) swap(f1, f2), swap(x, y);

		ret += query_sum(1, 1, n, f[f1], f[x]);

		x = father[f1], f1 = top[x];

	}

	if (x == y) return ret + query_sum(1, 1, n, f[x], f[y]);

	if (deep[x] > deep[y]) swap(x, y);

	return ret + query_sum(1, 1, n, f[x], f[y]);

}

int main(){

	scanf("%d%d", &n, &m);

	rep(i, 1, n) scanf("%lld", a + i);

	rep(i, 2, n){

		int x, y;

		scanf("%d%d", &x, &y);

		v[x].push_back(y);

		v[y].push_back(x);

	}

	dfs1(1, 0, 0);

	dfs2(1, 1);

	build(1, 1, n);

	while (m--){

		scanf("%d", &op);

		if (op == 1){

			scanf("%d%lld", &x, &y);

			update(1, 1, n, f[x], f[x], y);

		}

		else if (op == 2){

			scanf("%d%lld", &x, &y);

			update(1, 1, n, f[x], f[x] + sz[x] - 1, y);

		}

		else{

			scanf("%d", &x);

			printf("%lld\n", find_sum(x, 1));

		}

	}

	return 0;

}

第二种方法：

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)    for (int i(a); i <= (b); ++i)

#define dec(i, a, b)    for (int i(a); i >= (b); --i)

#define lson        	i << 1, L, mid

#define rson        	i << 1 | 1, mid + 1, R

typedef long long LL;

const int N = 300010;

LL a[N], sum[N << 2], lazy[N << 2], y;

int f[N], fp[N], son[N], deep[N], father[N], sz[N], top[N];

int x, tot, n, m, op;

vector <int> v[N];

void dfs1(int x, int fa, int dep){

	deep[x] = dep;

	father[x] = fa;

	son[x] = 0;

	sz[x] = 1;

	int ct = (int)v[x].size();

	rep(i, 0, ct - 1){

		int u = v[x][i];

		if (u == fa) continue;

		dfs1(u, x, dep + 1);

		sz[x] += sz[u];

		if (sz[son[x]] < sz[u]) son[x] = u;

	}

}

void dfs2(int x, int tp){

	top[x] = tp;

	f[x] = ++tot;

	fp[f[x]] = x;

	if (son[x]) dfs2(son[x], tp);

	int ct = (int)v[x].size();

	rep(i, 0, ct - 1){

		int u = v[x][i];

		if (u == father[x] || u == son[x]) continue;

		dfs2(u, u);

	}

}

inline void pushup(int i){ sum[i] = sum[i << 1] + sum[i << 1 | 1]; }

inline void pushdown(int i, int L, int R){

	sum[i] += lazy[i] * (R - L + 1);

	lazy[i << 1] += lazy[i];

	lazy[i << 1 | 1] += lazy[i];

	lazy[i] = 0;

}

void build(int i, int L, int R){

	if (L == R){ sum[i] = a[fp[L]]; return; }

	int mid = (L + R) >> 1;

	build(lson);

	build(rson);

	pushup(i);

}

void update(int i, int L, int R, int l, int r, LL val){

	if (l == L && R == r){

		lazy[i] += val;

		return ;

	}

	int mid = (L + R) >> 1;

	if (r <= mid) update(lson, l, r, val);

	else if (l > mid) update(rson, l, r, val);

	else{

		update(lson, l, mid, val);

		update(rson, mid + 1, r, val);

	}

	pushdown(i << 1, L, mid);

	pushdown(i << 1 | 1, mid + 1, R);

	pushup(i);

}

LL query_sum(int i, int L, int R, int l, int r){

	pushdown(i, L, R);

	if (L == l && R == r) return sum[i];

	int mid = (L + R) >> 1;

	if (r <= mid) return query_sum(lson, l, r);

	else if (l > mid) return query_sum(rson, l, r);

	else return query_sum(lson, l, mid) + query_sum(rson, mid + 1, r);

}

int main(){

	scanf("%d%d", &n, &m);

	rep(i, 1, n) scanf("%lld", a + i);

	rep(i, 2, n){

		int x, y;

		scanf("%d%d", &x, &y);

		v[x].push_back(y);

		v[y].push_back(x);

	}

	dfs1(1, 0, 0);

	dfs2(1, 1);

	build(1, 1, n);

	while (m--){

		scanf("%d", &op);

		if (op == 1){

			scanf("%d%lld", &x, &y);

			update(1, 1, n, f[x], f[x], y);

		}

		else if (op == 2){

			scanf("%d%lld", &x, &y);

			update(1, 1, n, f[x], f[x] + sz[x] - 1, y);

		}

		else{

			scanf("%d", &x);

			LL ans = 0;

			for (int i = x; i; i = father[top[i]])

				ans += query_sum(1, 1, n, f[top[i]], f[i]);

			printf("%lld\n", ans);

		}

	}

	return 0;

}

巴特西

BZOJ 4034 [HAOI2015]树上操作（树链剖分）

最新文章

热门文章