经验总结

  1. 首页 > 生活 > >

LOJ139 树链剖分

生活百科LOJ139 树链剖分

题目
感觉这已经不能说是模板了吧......
解析：
难点在于换根后对子树进行的操作，设rt为当前根节点，u为操作子树：
u=rt时，就是对整棵树操作，没事么好说的 。
rt不在u的子树范围内，操作对象就是u的子树 。
rt在u的子树范围内，操作范围就是整棵树减去u-rt路径上深度最小的点（可以用线段树维护该点）的子树（不包括u） 。
（可以画图模拟一下，注意这里我所说的某个节点的子树都是以1为根的情况） 。
【LOJ139 树链剖分】代码：
1 #include <bits/stdc++.h>2 #define ll long long3 using namespace std;4 const int N = 1e5 + 10, inf = 1e9;5 int head[N], to[N << 1], nxt[N << 1], tot;6 int n, m, cnt, rt = 1;7 ll val[N];8 int dep[N], size[N], top[N], fa[N], son[N], id[N], rev[N];9 int opt, a, b, c; 10 struct node { 11int minp; 12ll sum, lazy; 13 }t[N << 2]; 14 void add(int a, int b) { 15nxt[++ tot] = head[a], head[a] = tot, to[tot] = b; 16 } 17 void dfs1(int u, int f) { 18size[u] = 1; 19for (int i = head[u]; i; i = nxt[i]) { 20int v = to[i]; 21if (v == f) continue; 22fa[v] = u; 23dep[v] = dep[u] + 1; 24dfs1(v, u); 25size[u] += size[v]; 26if (size[v] > size[son[u]]) son[u] = v; 27} 28 } 29 void dfs2(int u, int t) { 30top[u] = t; 31id[u] = ++ cnt; 32rev[cnt] = u; 33if(!son[u]) return ; 34dfs2(son[u], t); 35for (int i = head[u]; i; i = nxt[i]) { 36int v = to[i]; 37if (v != fa[u] && v != son[u]) dfs2(v, v); 38} 39 } 40 namespace SegmentTree { 41#define mid ((l + r) >> 1) 42#define lson k << 1, l, mid 43#define rson k << 1 | 1, mid + 1, r 44int tmin(int a, int b) {//返回深度更小的点 45if (a == inf) return b; 46if (b == inf) return a; 47if (dep[a] < dep[b]) return a; 48else return b; 49} 50void pushup(int k) {//更新信息 51t[k].sum = t[k << 1].sum + t[k << 1 | 1].sum; 52t[k].minp = tmin(t[k << 1].minp, t[k << 1 | 1].minp); 53} 54void pushdown(int k, int l, int r) {//标记下传 55if (!t[k].lazy) return ; 56t[k << 1].lazy += t[k].lazy; 57t[k << 1 | 1].lazy += t[k].lazy; 58t[k << 1].sum += (mid - l + 1) * t[k].lazy; 59t[k << 1 | 1].sum += (r - mid) * t[k].lazy; 60t[k].lazy = 0; 61} 62void build(int k, int l, int r) {//建树 63if (l == r) { 64t[k].minp = rev[l]; 65t[k].sum = val[rev[l]]; 66return ; 67} 68build(lson), build(rson); 69pushup(k); 70} 71void update(int k, int l, int r, int L, int R, ll v) {//更新权值 72if (L <= l && R >= r) { 73t[k].sum += (r - l + 1) * v; 74t[k].lazy += v; 75return ; 76} 77pushdown(k, l, r); 78if (L <= mid) update(lson, L, R, v); 79if (R > mid) update(rson, L, R, v); 80pushup(k); 81} 82ll query(int k, int l, int r, int L, int R) { 83ll ans = 0; 84if (L <= l && R >= r) return t[k].sum; 85pushdown(k, l, r); 86if (L <= mid) ans += query(lson, L, R); 87if (R > mid) ans += query(rson, L, R); 88return ans; 89} 90int find(int k, int l, int r, int L, int R) { 91int x = inf; 92if (R < L) return inf; 93if (L <= l && R >= r) return t[k].minp;//返回树中节点编号 94if (L <= mid) x = tmin(x, find(lson, L, R)); 95if (R > mid) x = tmin(x, find(rson, L, R)); 96return x; 97} 98int lca(int a, int b) { 99while (top[a] != top[b]) {100if (dep[top[a]] < dep[top[b]]) swap(a, b);101a = fa[top[a]];102}103if (dep[a] > dep[b]) swap(a, b);104return a;105}106int Upto(int a, int b) {//返回u-r链上(除u)深度最小的点107int ans = inf;108while (top[a] != top[b]) {109if (dep[top[a]] < dep[top[b]]) swap(a, b);110if (top[a] != b) ans = tmin(ans, find(1, 1, n, id[top[a]], id[a]));111else ans = tmin(ans, find(1, 1, n, id[top[a]] + 1, id[a]));//不能包括b112a = fa[top[a]];113}114if (dep[a] > dep[b]) swap(a, b);115ans = tmin(ans, find(1, 1, n, id[a] + 1, id[b]));116return ans;117}118int check(int a) {//判断三种类型中的哪一种119if (a == rt) return 0;120int L = lca(a, rt);121if (L == a) return Upto(a, rt);122else return -1;123}124void Add_Chain(int a, int b, ll w) {//修改路径上的节点权值125while (top[a] != top[b]) {126if (dep[top[a]] < dep[top[b]]) swap(a, b);127update(1, 1, n, id[top[a]], id[a], w);128a = fa[top[a]];129}130if (dep[a] > dep[b]) swap(a, b);131update(1, 1, n, id[a], id[b], w);132}133ll Ask_Chain(int a, int b) {//查询路径节点权值和134ll ans = 0;135while (top[a] != top[b]) {136if(dep[top[a]] < dep[top[b]]) swap(a, b);137ans += query(1, 1, n, id[top[a]], id[a]);138a = fa[top[a]];139}140if (dep[a] > dep[b]) swap(a, b);141ans += query(1, 1, n, id[a], id[b]);142return ans;143}144void Add_Tree(int u, ll v) {//修改子树权值145int type = check(u);146if (!type) update(1, 1, n, 1, n, v);147else if (type > 0) {148update(1, 1, n, 1, n, v);149update(1, 1, n, id[type], id[type] + size[type] - 1, -v);150} else update(1, 1, n, id[u], id[u] + size[u] - 1, v);151}152ll Ask_Tree(int u) {153int type = check(u);154if (!type) return query(1, 1, n, 1, n);155else if (type > 0) {156//一定要写type>0,一开始我写的type(实际意思是type!=0)157//不然一直都是RE158ll ans = query(1, 1, n, id[type], id[type] + size[type] - 1);159return query(1, 1, n, 1, n) - ans;160} else return query(1, 1, n, id[u], id[u] + size[u] - 1);161}162 }163 using namespace SegmentTree;164 int main() {165scanf("%d", &n);;166for (int i = 1; i <= n; i ++) scanf("%lld", &val[i]);167for (int i = 2; i <= n; i ++) {168scanf("%d", &a);169add(i, a), add(a, i);170}171dep[1] = 1;172dfs1(1, 0);173dfs2(1, 1);174build(1, 1, n);175scanf("%d", &m);176while (m --) {177scanf("%d", &opt);178if (opt == 1) {179scanf("%d", &a);180rt = a;181} else if (opt == 2) {182scanf("%d %d %d", &a, &b, &c);183Add_Chain(a, b, c);184} else if (opt == 3) {185scanf("%d %d", &a, &b);186Add_Tree(a, b);187} else if (opt == 4) {188scanf("%d %d", &a, &b);189printf("%lld\n", Ask_Chain(a, b));190} else {191scanf("%d", &a);192printf("%lld\n", Ask_Tree(a));193}194}195return 0;196 }

经验总结扩展阅读


上一篇：什么花花语是错过的爱

下一篇：常用的论证方法有哪些