HDU5173 GTY's game II
bc的题。今天bc又挂了。这题没有写完，然后b题fst了。伤心啊。
其实思路比较简单。直接链剖dfs序上把所有区间找出来swap就好了。不过代码实现起来还是比较麻烦的，很容易绕晕。加上smt久了没写手生了，于是就调了一晚上。唉，我还是太年轻了。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 struct node { 9 int v, s, sz, w, rv; 10 node *ls, *rs; 11 inline void update() { 12 sz = 1; 13 s = v; 14 if (ls) { 15 sz += ls-> sz; 16 s += ls-> s; 17 } 18 if (rs) { 19 sz += rs-> sz; 20 s += rs-> s; 21 } 22 } 23 inline void fix() { 24 if (rv) { 25 swap(ls, rs); 26 if (ls) 27 ls-> rv ^= 1; 28 if (rs) 29 rs-> rv ^= 1; 30 rv = 0; 31 } 32 } 33 }; 34 typedef pair <node*, node*> npr; 35 36 const int maxn = 80009; 37 38 #define szof(p) ((p)?(p->sz):0) 39 #define sof(p) ((p)?(p->s):0) 40 node nlst[maxn << 1], *np(nlst); 41 node* newNode(int v) { 42 np-> ls = np-> rs = 0; 43 np-> v = np-> s = v; 44 np-> sz = 1; 45 np-> rv = 0; 46 #ifdef WIN32 47 np-> w = (rand() << 16) | rand(); 48 #else 49 np-> w = rand(); 50 #endif 51 return np ++; 52 } 53 node* merge(node* p, node* q) { 54 if (p) 55 p-> fix(); 56 else 57 return q; 58 if (q) 59 q-> fix(); 60 else 61 return p; 62 if (p-> w > q-> w) { 63 p-> rs = merge(p-> rs, q); 64 p-> update(); 65 return p; 66 } 67 else { 68 q-> ls = merge(p, q-> ls); 69 q-> update(); 70 return q; 71 } 72 } 73 npr split(node* p, int k) { 74 if (!k) 75 return npr(0, p); 76 else if (!p || p-> sz == k) 77 return npr(p, 0); 78 else { 79 p-> fix(); 80 if (k <= szof(p-> ls)) { 81 npr g(split(p-> ls, k)); 82 p-> ls = g. second; 83 p-> update(); 84 return npr(g. first, p); 85 } 86 else { 87 npr g(split(p-> rs, k - szof(p-> ls) - 1)); 88 p-> rs = g. first; 89 p-> update(); 90 return npr(p, g. second); 91 } 92 } 93 } 94 int smtQry(node* p, int k) { 95 int s(0); 96 while (p && k) { 97 p-> fix(); 98 if (k <= szof(p-> ls)) 99 p = p-> ls; 100 else 101 s += sof(p-> ls) + p-> v, k -= szof(p-> ls) + 1, p = p-> rs; 102 } 103 return s; 104 } 105 106 struct edge { 107 int t; 108 edge *next; 109 }; 110 edge *head[maxn], elst[maxn << 1], *ep(elst); 111 inline void addEdge(int u, int v) { 112 ep-> t = v; 113 ep-> next = head[u]; 114 head[u] = ep ++; 115 } 116 117 int v[maxn], n, m; 118 int tc, fa[maxn], d[maxn], sz[maxn], fs[maxn], fc[maxn], ch[maxn]; 119 int dfb[maxn], dfo[maxn]; 120 node *rt, *remp; 121 122 void divide() { 123 static int stc[maxn]; 124 int tst(1), dfn(0); 125 memset(fa, 0, sizeof(fa)); 126 stc[tst] = 1; 127 while (tst) { 128 int p(stc[tst --]); 129 dfo[++ dfn] = p; 130 for (edge* e = head[p]; e; e = e-> next) 131 if (e-> t ^ fa[p]) { 132 fa[e-> t] = p; 133 d[e-> t] = d[p] + 1; 134 stc[++ tst] = e-> t; 135 } 136 } 137 tc = 0; 138 for (int i = n; i; -- i) { 139 int p(dfo[i]); 140 fs[p] = -1; 141 sz[p] = 1; 142 for (edge* e = head[p]; e; e = e-> next) 143 if (fa[e-> t] == p) { 144 sz[p] += sz[e-> t]; 145 if (fs[p] == -1 || sz[e-> t] > sz[fs[p]]) 146 fs[p] = e-> t; 147 } 148 if (fs[p] == -1) 149 fc[p] = ++ tc; 150 else 151 fc[p] = fc[fs[p]]; 152 ch[fc[p]] = p; 153 } 154 stc[tst = 1] = 1; 155 dfn = 0; 156 while (tst) { 157 int p(stc[tst --]); 158 dfo[++ dfn] = p; 159 dfb[p] = dfn; 160 for (edge* e = head[p]; e; e = e-> next) 161 if (fa[e-> t] == p && e-> t != fs[p]) 162 stc[++ tst] = e-> t; 163 if (fs[p] != -1) 164 stc[++ tst] = fs[p]; 165 } 166 rt = 0; 167 for (int i = 1; i <= n; ++ i) 168 rt = merge(rt, newNode(v[dfo[i]])); 169 remp = 0; 170 for (int i = 1; i <= n; ++ i) 171 remp = merge(remp, newNode(-1)); 172 } 173 174 int query(int u, int v) { 175 int s(0); 176 while (fc[u] ^ fc[v]) 177 if (d[ch[fc[u]]] > d[ch[fc[v]]]) { 178 s += smtQry(rt, dfb[u]) - smtQry(rt, dfb[ch[fc[u]]] - 1); 179 u = fa[ch[fc[u]]]; 180 } 181 else { 182 s += smtQry(rt, dfb[v]) - smtQry(rt, dfb[ch[fc[v]]] - 1); 183 v = fa[ch[fc[v]]]; 184 } 185 if (d[u] < d[v]) 186 s += smtQry(rt, dfb[v]) - smtQry(rt, dfb[u] - 1); 187 else 188 s += smtQry(rt, dfb[u]) - smtQry(rt, dfb[v] - 1); 189 return s; 190 } 191 192 bool checkTree(node* p, char e) { 193 if (p) { 194 if (p-> rv) { 195 checkTree(p-> rs, 32); 196 printf("%d%c", p-> v, e); 197 checkTree(p-> ls, 32); 198 } 199 else { 200 checkTree(p-> ls, 32); 201 printf("%d%c", p-> v, e); 202 checkTree(p-> rs, 32); 203 } 204 } 205 return 0; 206 } 207 208 typedef pair <int, int> rpr; 209 rpr ra[maxn], rb[maxn]; 210 void flip(int u, int v) { 211 int tra(0), trb(0); 212 while (fc[u] ^ fc[v]) { 213 if (d[ch[fc[u]]] > d[ch[fc[v]]]) { 214 ra[tra ++] = rpr(dfb[ch[fc[u]]], dfb[u]); 215 u = fa[ch[fc[u]]]; 216 } 217 else { 218 rb[trb ++] = rpr(dfb[ch[fc[v]]], dfb[v]); 219 v = fa[ch[fc[v]]]; 220 } 221 } 222 if (d[u] < d[v]) 223 rb[trb ++] = rpr(dfb[u], dfb[v]); 224 else 225 ra[tra ++] = rpr(dfb[v], dfb[u]); 226 node *cr(0); 227 for (int i = 0; i < tra; ++ i) { 228 npr x = split(rt, ra[i]. first - 1); 229 npr y = split(x. second, ra[i]. second - ra[i]. first + 1); 230 cr = merge(y. first, cr); 231 npr z = split(remp, ra[i]. second - ra[i]. first + 1); 232 remp = z. second; 233 x. second = merge(z. first, y. second); 234 rt = merge(x. first, x. second); 235 } 236 if (cr) 237 cr-> rv ^= 1; 238 for (int i = trb - 1; i >= 0; -- i) { 239 npr x = split(rt, rb[i]. first - 1); 240 npr y = split(x. second, rb[i]. second - rb[i]. first + 1); 241 cr = merge(cr, y. first); 242 npr z = split(remp, rb[i]. second - rb[i]. first + 1); 243 remp = z. second; 244 x. second = merge(z. first, y. second); 245 rt = merge(x. first, x. second); 246 } 247 if (cr) 248 cr-> rv ^= 1; 249 for (int i = 0; i < tra; ++ i) { 250 npr x = split(rt, ra[i]. first - 1); 251 npr y = split(x. second, ra[i]. second - ra[i]. first + 1); 252 npr z = split(cr, ra[i]. second - ra[i]. first + 1); 253 cr = z. second; 254 if (z. first) 255 z. first-> rv ^= 1; 256 x. second = merge(z. first, y. second); 257 rt = merge(x. first, x. second); 258 remp = merge(remp, y. first); 259 } 260 if (cr) 261 cr-> rv ^= 1; 262 for (int i = 0; i < trb; ++ i) { 263 npr x = split(rt, rb[i]. first - 1); 264 npr y = split(x. second, rb[i]. second - rb[i]. first + 1); 265 npr z = split(cr, rb[i]. second - rb[i]. first + 1); 266 cr = z. second; 267 if (z. first) 268 z. first-> rv ^= 1; 269 x. second = merge(z. first, y. second); 270 rt = merge(x. first, x. second); 271 remp = merge(remp, y. first); 272 } 273 } 274 275 int main() { 276 #ifndef ONLINE_JUDGE 277 freopen("in.txt", "r", stdin); 278 #endif 279 280 memset(head, 0, sizeof(head)); 281 scanf("%d%d", &n, &m); 282 for (int i = 1; i <= n; ++ i) 283 scanf("%d", v + i); 284 for (int i = 1; i < n; ++ i) { 285 int u, v; 286 scanf("%d%d", &u, &v); 287 addEdge(u, v); 288 addEdge(v, u); 289 } 290 divide(); 291 while (m --) { 292 int opt, u, v; 293 scanf("%d%d%d", &opt, &u, &v); 294 if (opt == 0) 295 printf("%d\n", query(u, v)); 296 else 297 flip(u, v); 298 } 299 } 300
评论 (0)
