BZOJ3435 [Wc2014]紫荆花之恋
想起去年在考场上完全没有思路不想写数据结构于是骗了30分。现在想想当初还是naive。
这题看上去就是点分治。因为要动态加点所以要动态。然后利用替罪羊树的方法重构树上的一团东西（不能叫团，否则命名重复了）。
本来以为要写很久，结果也没写多久。奇怪的是，把maintain展开到insert里面之后就跑得飞快了，否则过不到而且根本跑不下来9和10。又丑了郁闷。
1 #include <cstdio> 2 #include <cctype> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int buf_len = 4000; 9 const size_t buf_size = buf_len * sizeof(char); 10 char buf[buf_len], *bufb(buf), *bufe(buf + 1); 11 #define readBuf() { \ 12 if (++ bufb == bufe) \ 13 bufe = (bufb = buf) + fread(buf, 1, buf_size, stdin); \ 14 } 15 #define readInt(_x_) { \ 16 register int _s_(0); \ 17 do { \ 18 readBuf(); \ 19 } while (!isdigit(*bufb)); \ 20 do { \ 21 _s_ = _s_ * 10 + *bufb - 48; \ 22 readBuf(); \ 23 } while (isdigit(*bufb)); \ 24 _x_ = _s_; \ 25 } 26 27 struct edge { 28 int t, v; 29 edge *next; 30 }; 31 struct sbt_node { 32 int vl, sz; 33 sbt_node *ls, *rs; 34 }; 35 36 typedef long long dint; 37 38 #ifdef WIN32 39 #define lld "%I64d" 40 #else 41 #define lld "%lld" 42 #endif 43 #define _l (long long int) 44 45 const int maxn = 100009; 46 const int fmod = 1e9; 47 const int maxl = 19; 48 const int maxnd = maxn * maxl * 2; 49 const int balc = 3; 50 const double ublim = 0.9; 51 const int inf = 0x3f3f3f3f; 52 53 dint lans; 54 int n; 55 int ath[maxn][maxl], drt[maxn], dep[maxn]; 56 int bd[maxn], bsz[maxn], bfa[maxn], br[maxn], r[maxn]; 57 int stsz[maxn], vis[maxn], vist; 58 sbt_node slst[maxnd], *sstc[maxnd], **sp, *brt[maxn], *prt[maxn]; 59 edge *head[maxn], elst[maxn << 1], *ep(elst); 60 61 void pre() { 62 for (int i = 0; i < maxnd; ++ i) { 63 sstc[i] = slst + i; 64 slst[i]. ls = slst[i]. rs = 0; 65 } 66 sp = sstc; 67 vist = 0; 68 memset(vis, 0, sizeof(vis)); 69 } 70 71 inline void addEdge(int u, int v, int w) { 72 ep-> t = v; 73 ep-> v = w; 74 ep-> next = head[u]; 75 head[u] = ep ++; 76 } 77 78 #define szof(_p_) ((_p_)?(_p_->sz):0) 79 inline sbt_node* allocNode() { 80 static sbt_node* ret; 81 ret = *(sp ++); 82 if (ret-> ls) 83 *(-- sp) = ret-> ls; 84 if (ret-> rs) 85 *(-- sp) = ret-> rs; 86 return ret; 87 } 88 inline void lRot(sbt_node* &p) { 89 register sbt_node* q(p-> ls); 90 p-> ls = q-> rs; 91 q-> rs = p; 92 q-> sz = p-> sz; 93 p-> sz = szof(p-> ls) + szof(p-> rs) + 1; 94 p = q; 95 } 96 inline void rRot(sbt_node* &p) { 97 register sbt_node* q(p-> rs); 98 p-> rs = q-> ls; 99 q-> ls = p; 100 q-> sz = p-> sz; 101 p-> sz = szof(p-> ls) + szof(p-> rs) + 1; 102 p = q; 103 } 104 inline void sbtIns(sbt_node* &p, int v0) { 105 if (!p) { 106 p = allocNode(); 107 p-> ls = p-> rs = 0; 108 p-> sz = 1; 109 p-> vl = v0; 110 } 111 else { 112 ++ p-> sz; 113 if (v0 < p-> vl) { 114 sbtIns(p-> ls, v0); 115 if (szof(p-> ls) > szof(p-> rs) + balc) 116 lRot(p); 117 } 118 else { 119 sbtIns(p-> rs, v0); 120 if (szof(p-> ls) + balc < szof(p-> rs)) 121 rRot(p); 122 } 123 } 124 } 125 int sbtCntLower(sbt_node* p, int v0) { 126 int s(0); 127 while (p) 128 if (v0 < p-> vl) 129 p = p-> ls; 130 else 131 s += szof(p-> ls) + 1, p = p-> rs; 132 return s; 133 } 134 135 int LCA(int u, int v) { 136 if (dep[u] < dep[v]) 137 swap(u, v); 138 for (int i = maxl - 1; i >= 0; -- i) 139 if (dep[ath[u][i]] >= dep[v]) 140 u = ath[u][i]; 141 if (u == v) 142 return u; 143 for (int i = maxl - 1; i >= 0; -- i) 144 if (ath[u][i] ^ ath[v][i]) { 145 u = ath[u][i]; 146 v = ath[v][i]; 147 } 148 return ath[u][0]; 149 } 150 inline int dist(int u, int v) { 151 int a(LCA(u, v)); 152 return drt[u] + drt[v] - drt[a] * 2; 153 } 154 155 void insEach(sbt_node* q, sbt_node* &x, int mn) { 156 static sbt_node* stc[maxn]; 157 int tst(1); 158 stc[1] = q; 159 while (tst) { 160 sbt_node* p(stc[tst --]); 161 sbtIns(x, p-> vl + mn); 162 if (p-> ls) 163 stc[++ tst] = p-> ls; 164 if (p-> rs) 165 stc[++ tst] = p-> rs; 166 } 167 } 168 int build(int pbd, int pbr, int pbf) { 169 static int q[maxn], fr[maxn], dst[maxn]; 170 int hd(0), tl(1), ct(0), cs(inf); 171 q[0] = pbr; 172 fr[pbr] = 0; 173 dst[pbr] = 0; 174 while (hd < tl) { 175 int p(q[hd ++]); 176 for (edge* e = head[p]; e; e = e-> next) 177 if (bd[e-> t] == inf && e-> t != fr[p]) { 178 fr[e-> t] = p; 179 dst[e-> t] = dst[p] + e-> v; 180 q[tl ++] = e-> t; 181 } 182 } 183 for (int ti = tl - 1, p; ti >= 0; -- ti) { 184 int ms(1); 185 p = q[ti]; 186 stsz[p] = 1; 187 for (edge* e = head[p]; e; e = e-> next) 188 if (bd[e-> t] == inf && e-> t != fr[p]) { 189 stsz[p] += stsz[e-> t]; 190 if (ms < stsz[e-> t]) 191 ms = stsz[e-> t]; 192 } 193 if (ms < tl - stsz[p]) 194 ms = tl - stsz[p]; 195 if (ms < cs) { 196 cs = ms; 197 ct = p; 198 } 199 } 200 for (int ti = 0, p; ti < tl; ++ ti) { 201 p = q[ti]; 202 sbtIns(prt[ct], dst[p] - r[p]); 203 } 204 bd[ct] = pbd; 205 bsz[ct] = tl; 206 bfa[ct] = pbf; 207 br[ct] = pbr; 208 sbtIns(brt[ct], -r[ct]); 209 for (edge* e = head[ct]; e; e = e-> next) 210 if (bd[e-> t] == inf) { 211 int nr(build(pbd + 1, e-> t, ct)); 212 insEach(prt[nr], brt[ct], e-> v); 213 } 214 return ct; 215 } 216 217 void rebuild(int p0, int pbd, int pbr, int pbf) { 218 static int q[maxn]; 219 int hd(0), tl(1); 220 ++ vist; 221 vis[p0] = vist; 222 q[0] = p0; 223 while (hd < tl) { 224 int p(q[hd ++]); 225 *(-- sp) = brt[p]; 226 *(-- sp) = prt[p]; 227 brt[p] = 0; 228 prt[p] = 0; 229 for (edge* e = head[p]; e; e = e-> next) 230 if (bd[e-> t] > pbd && vis[e-> t] < vist) { 231 vis[e-> t] = vist; 232 q[tl ++] = e-> t; 233 } 234 } 235 for (int i = 0; i < tl; ++ i) 236 bd[q[i]] = inf; 237 build(pbd, pbr, pbf); 238 } 239 240 void addNode(int p) { 241 brt[p] = 0; 242 sbtIns(brt[p], -r[p]); 243 prt[p] = 0; 244 sbtIns(prt[p], -r[p]); 245 if (p == 1) { 246 bd[p] = 1; 247 bsz[p] = 1; 248 bfa[p] = 0; 249 br[p] = 1; 250 } 251 else { 252 register int fa(ath[p][0]); 253 bd[p] = bd[fa] + 1; 254 bsz[p] = 1; 255 bfa[p] = fa; 256 br[p] = p; 257 int q(fa), l(p), ubp, dt(0); 258 double ubv(0); 259 while (q) { 260 ++ bsz[q]; 261 if ((double)bsz[l] / bsz[q] > ubv) { 262 ubv = (double)bsz[l] / bsz[q]; 263 ubp = q; 264 } 265 int d0(dist(p, q)); 266 sbtIns(brt[q], d0 - r[p]); 267 sbtIns(prt[q], dist(br[q], p) - r[p]); 268 dt += sbtCntLower(brt[q], r[p] - d0) - sbtCntLower(prt[l], r[p] - d0 - dist(br[l], q)); 269 l = q; 270 q = bfa[q]; 271 } 272 lans += dt; 273 if (ubv > ublim) 274 rebuild(ubp, bd[ubp], br[ubp], bfa[ubp]); 275 } 276 } 277 278 int main() { 279 #ifndef ONLINE_JUDGE 280 freopen("in.txt", "r", stdin); 281 #endif 282 283 pre(); 284 readInt(n); 285 readInt(n); 286 lans = 0; 287 for (int i = 1; i <= n; ++ i) { 288 int fa; 289 readInt(fa); 290 readInt(drt[i]); 291 readInt(r[i]); 292 if (i > 1) { 293 fa ^= lans % fmod; 294 dep[i] = dep[fa] + 1; 295 addEdge(fa, i, drt[i]); 296 addEdge(i, fa, drt[i]); 297 drt[i] += drt[fa]; 298 ath[i][0] = fa; 299 for (int j = 1; j < maxl; ++ j) 300 ath[i][j] = ath[ath[i][j - 1]][j - 1]; 301 } 302 else { 303 dep[i] = 1; 304 } 305 addNode(i); 306 printf(lld "\n", lans); 307 } 308 } 309
评论 (0)
