首页 > 代码库 > HDOJ 3966 树链剖分

HDOJ 3966 树链剖分

链接:

http://acm.hdu.edu.cn/showproblem.php?pid=3966

代码:

  1 #include <map>
  2 #include <set>
  3 #include <cmath>
  4 #include <queue>
  5 #include <stack>
  6 #include <cstdio>
  7 #include <string>
  8 #include <vector>
  9 #include <cstdlib>
 10 #include <cstring>
 11 #include <sstream>
 12 #include <iostream>
 13 #include <algorithm>
 14 #include <functional>
 15 using namespace std;
 16 #define rep(i,a,n) for (int i=a;i<n;i++)
 17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
 18 #define all(x) (x).begin(),(x).end()
 19 #define pb push_back
 20 #define mp make_pair
 21 #define lson l,m,rt<<1  
 22 #define rson m+1,r,rt<<1|1 
 23 typedef long long ll;
 24 typedef vector<int> VI;
 25 typedef pair<int, int> PII;
 26 const ll MOD = 1e9 + 7;
 27 const int INF = 0x3f3f3f3f;
 28 const int MAXN = 5e4 + 7;
 29 // head
 30 
 31 int n, m, p;
 32 int a[MAXN];
 33 VI G[MAXN];
 34 
 35 int tim;
 36 int siz[MAXN];    //保存以x为根的子树节点个数
 37 int top[MAXN];    //保存当前节点的所在链的顶端节点
 38 int son[MAXN];    //保存重儿子
 39 int dep[MAXN];    //保存当前节点的深度
 40 int par[MAXN];    //保存当前节点的父亲
 41 int tid[MAXN];    //保存树中每个节点剖分后的新编号
 42 int ran[MAXN];    //保存当前节点在线段树中的位置
 43 
 44 void init() {
 45     rep(i, 0, MAXN) {
 46         G[i].clear();
 47         tim = 0;
 48         siz[i] = top[i] = son[i] = dep[i] = par[i] = tid[i] = ran[i] = 0;
 49     }
 50 }
 51 
 52 void dfs1(int u, int pre){
 53     siz[u] = 1;
 54     par[u] = pre;    
 55     dep[u] = dep[pre] + 1;
 56     rep(i, 0, G[u].size()) {
 57         int v = G[u][i];
 58         if (v != par[u]){
 59             dfs1(v, u);
 60             siz[u] += siz[v];
 61             if (son[u] == 0 || siz[v] > siz[son[u]])
 62                 son[u] = v;
 63         }
 64     }
 65 }
 66 
 67 void dfs2(int u, int tp) {
 68     top[u] = tp;
 69     tid[u] = ++tim;
 70     ran[tid[u]] = u;
 71     if (son[u]) dfs2(son[u], tp);
 72     rep(i, 0, G[u].size()) {
 73         int v = G[u][i];
 74         if (v != son[u] && v != par[u])
 75             dfs2(v, v);
 76     }
 77 }
 78 
 79 int tree[MAXN << 2], lazy[MAXN << 2];
 80 
 81 void pushdown(int rt, int m) {
 82     if (lazy[rt] != 0) {
 83         tree[rt << 1] += lazy[rt] * (m - (m >> 1));
 84         tree[rt << 1 | 1] += lazy[rt] * (m >> 1);
 85         lazy[rt << 1] += lazy[rt];
 86         lazy[rt << 1 | 1] += lazy[rt];
 87         lazy[rt] = 0;
 88     }
 89 }
 90 
 91 void build(int l, int r, int rt) {
 92     lazy[rt] = 0;
 93     if (l == r) {
 94         tree[rt] = a[ran[l]];
 95         return;
 96     }
 97     int m = (l + r) >> 1;
 98     build(lson);
 99     build(rson);
100 }
101 
102 int query(int k, int l, int r, int rt) {
103     if (l == r) return tree[rt];
104     pushdown(rt, r - l + 1);
105     int m = (l + r) >> 1;
106     if (k <= m) return query(k, lson);
107     else return query(k, rson);
108 }
109 
110 void update(int L, int R, int x, int l, int r, int rt)  {
111     if (L <= l && r <= R) {
112         tree[rt] += (r - l + 1) *x;
113         lazy[rt] += x;
114         return;
115     }
116     pushdown(rt, r - l + 1);
117     int m = (l + r) >> 1;
118     if (L <= m) update(L, R, x, lson);
119     if (R > m) update(L, R, x, rson);
120 }
121 
122 void change(int x, int y, int val)
123 {
124     while (top[x] != top[y]){
125         if (dep[top[x]] < dep[top[y]]) swap(x, y);
126         update(tid[top[x]], tid[x], val, 1, n, 1);
127         x = par[top[x]];
128     }
129     if (dep[x] > dep[y]) swap(x, y);
130     update(tid[x], tid[y], val, 1, n, 1);
131 }
132 
133 int main() {
134     while (cin >> n >> m >> p) {
135         init();
136         rep(i, 1, n + 1) scanf("%d", a + i);
137         while (m--) {
138             int u, v;
139             scanf("%d%d", &u, &v);
140             G[u].pb(v);
141             G[v].pb(u);
142         }
143         dfs1(1, 0);
144         dfs2(1, 1);
145         build(1, n, 1);
146         while (p--) {
147             char s[2];
148             scanf("%s", s);
149             if (s[0] == Q) {
150                 int c;
151                 scanf("%d", &c);
152                 printf("%d\n", query(tid[c], 1, n, 1));
153             }
154             else {
155                 int c1, c2, k;
156                 scanf("%d%d%d", &c1, &c2, &k);
157                 if (s[0] == I) change(c1, c2, k);
158                 else change(c1, c2, -k);
159             }
160         }    
161     }
162     return 0;
163 }

 

HDOJ 3966 树链剖分