Hdu 3966(树链剖分)

hdu 3966

裸树剖+线段树维护,while写成if, 数组开小搞得我调试了好久。。静态查错真的不能快了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i, j, k) for (i=(j);i<=(k);i++)
#define fd(i, k, j) for (i=(k);i>=(j);i--)
#define fe(i, u) for (i=head[u];i!=-1;i=e[i].next)
#define rd(a) scanf("%d", &a)
#define rd2(a, b) scanf("%d%d", &a, &b)
#define rd3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "hdu3966"
using namespace std;
const int MAXN = 50000 + 5;
struct date{int to, next;}e[MAXN*2];
int head[MAXN], cnt;
int n, m, Q, wi[MAXN];
int siz[MAXN], top[MAXN], p[MAXN], son[MAXN], fa[MAXN], dep[MAXN], pre;
void dfs1(int u, int p) {
int i;
siz[u] = 1, fa[u] = p, dep[u] = dep[p] + 1;
fe (i, u) {
int v = e[i].to;
if (v!=p) {
dfs1(v, u);
siz[u] += siz[v];
if (son[u]==-1||siz[son[u]]<siz[v]) son[u] = v;
}
}
}
void dfs2(int u, int chain) {
int i;
p[u] = ++pre, top[u] = chain;
if (son[u]!=-1) {
dfs2(son[u], chain);
fe (i, u) {
int v = e[i].to;
if (v!=fa[u]&&v!=son[u]) dfs2(v, v);
}
}
}
int sumv[MAXN*4], addv[MAXN*4];
void pushup(int o) {
int lc = o*2, rc = o*2+1;
sumv[o] = sumv[lc] + sumv[rc];
}
void pushdown(int o, int len) {
int lc = o*2, rc = o*2+1;
if (addv[o]) {
addv[lc] += addv[o], addv[rc] += addv[o];
sumv[lc] += (len-len/2)*addv[o], sumv[rc] += (len/2)*addv[o];
addv[o] = 0;
}
}
void update(int o, int l, int r, int x, int y, int v) {
int lc = o*2, rc = o*2+1, M = (l+r)/2;
if (x<=l&&r<=y) {
addv[o] += v;
sumv[o] += (r-l+1)*v;
return ;
}
pushdown(o, r-l+1);
if (x<=M) update(lc, l, M, x, y, v);
if (M<y) update(rc, M+1, r, x, y, v);
pushup(o);
}
int query(int o, int l, int r, int p) {
int lc = o*2, rc = o*2+1, M = (l+r)/2;
if (l==r) return sumv[o];
pushdown(o, r-l+1);
if (p<=M) return query(lc, l, M, p); else if (M<p) return query(rc, M+1, r, p);
}
void add(int u, int v, int c) {
int f1 = top[u], f2 = top[v];
while (f1!=f2) {
if (dep[f1]<dep[f2]) swap(f1, f2), swap(u, v);
update(1,1,n,p[f1],p[u],c);
u = fa[f1];
f1 = top[u];
}
if (dep[u]<dep[v]) swap(u, v);
update(1,1,n,p[v],p[u],c);
}
void ins(int u, int v) {
cnt++; e[cnt].to = v, e[cnt].next = head[u], head[u] = cnt;
cnt++; e[cnt].to = u, e[cnt].next = head[v], head[v] = cnt;
}
void init() {
int i; cnt = pre = 0;
fo (i, 1, n) head[i] = son[i] = -1, siz[i] = top[i] = p[i] = fa[i] = dep[i] = 0;
fo (i, 1, 2*n) e[i].to = 0, e[i].next = -1;
fo (i, 1, n) rd(wi[i]);
fo (i, 1, n*4) sumv[i] = addv[i] = 0;
fo (i, 1, m) {
int a, b; rd2(a, b), ins(a, b);
}
dfs1(1, 0), dfs2(1, 1);
}
void solve() {
int i;
fo (i, 1, n) add(i,i,wi[i]);
fo (i, 1, Q) {
int c1, c2, k; char ch[5]; scanf("%s", ch);
if (ch[0]=='I') {
rd3(c1, c2, k);
add(c1, c2, k);
} else if (ch[0]=='D') {
rd3(c1, c2, k);
add(c1, c2, -k);
} else if (ch[0]=='Q') {
rd(k);
printf("%d\n", query(1,1,n,p[k]));
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);freopen(FN2".out","w",stdout);
#endif
while (rd3(n, m, Q)==3) init(), solve();
return 0;
}

------ 本文结束 ------