傳送門：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=620

絕世難題（一） 可愛的仙人掌

難度級別：E； 運行時間限制：1000ms； 運行空間限制：262144KB； 代碼長度限制：2000000B

試題描述

---“神犇是怎么樣的。。。” ---“神犇就是這種**題拿過來半小時隨便A。。。(??????)??” ? 絕世難題之可愛的仙人掌 -------------------------我是題目和吐槽的分割線------------------------- ? chx童鞋最近迷上了圖論中的環(huán)，結果有一天他做夢都夢見了環(huán)。。。（ˉ﹃ˉ） ---“你最近一直研究我啊那你知道我有什么小名嘛？(,,? ? ?,,)” ---“噗。。。我怎么知道你告訴我唄。。。Σ( ° △ °|||)︴” ---“其實嘛，我的小名叫做仙人掌了啊~” 噗。。。chx腦中不禁腦補了一下。。。(??･з･?) 噗噗噗。。。chx心想好吧你說是就算是吧(⊙ ▽ ⊙) ---“其實呢，在一個無向連通圖中呢，如果每一條邊都只屬于一個簡單環(huán)，我們就把這個圖叫做仙人掌。。。如果圖中每一個連通塊都是一個萌萌噠仙人掌且沒有自環(huán)，那么我們就把這個圖稱作是沙漠。。。” 呵呵。。。好吧真的 好好好形象啊！！！(??????)?? 如果一個無向圖的每個連通塊都是個仙人掌，且不存在自環(huán)，我們就稱之為沙漠。 現(xiàn)在呢，為了證明你是玩轉(zhuǎn)仙人掌的神犇，chx給你 n 個結點，從 1 到 n 標號。 初始時沒有任何邊，且每個結點 i 有個權值 wi (wi>0) 。每次進行如下操作之一： ? link v uw：在結點 v,u 間連一條權值為 w 的邊。 1≤v,u≤n 且 w 為正整數(shù)。 如果連邊完成后圖仍為沙漠，則輸出 "ok"（不含引號）。 否則操作非法，撤銷此次操作并輸出 "failed"（不含引號）。 ? cut v uw：在結點 v,u 間刪掉一條權值為 w 的邊。 1≤v,u≤n 且 w 為正整數(shù)。 如果存在這樣的邊則輸出 "ok"（不含引號）（如果有多條權值為 w 的邊刪去任意一條）。 否則操作非法，不進行操作并輸出 "failed"（不含引號）。 ? query1 vu：查詢結點 v 到結點 u 的最短路信息。 1≤v,u≤n。 輸出兩個用空格隔開的整數(shù) min,σ，分別代表最短路上點權的最小值、和。 如果沒有路可到達則 min=?1,σ=?1。 如果最短路不唯一則 min=?2,σ=?2。 ? query2 vu：查詢以結點 v 為根，子仙人掌 u 的信息。 1≤v,u≤n。 以結點 v 為根，子仙人掌 u 的定義是，刪掉v 到 u 之間的所有簡單路徑上的邊之后，u 所在的連通塊。 輸出兩個用空格隔開的整數(shù) min,σ，分別代表子仙人掌 u 中點權的最小值、和。 如果 v,u 不連通則 min=?1,σ=?1。 ? add1 v ud：把結點 v 到結點 u 的最短路上的每一個結點的權值都加上 d。 1≤v,u≤n 且 d 為正整數(shù)。 如果有路可到達且最短路唯一，則輸出 "ok"（不含引號） 否則操作非法，不進行操作并輸出 "failed"（不含引號）。 ? add2 v ud：把以結點 v 為根，子仙人掌 u 的每一個結點的權值都加上 d。 1≤v,u≤n 且 d 為正整數(shù)。 如果 v,u 在同一個連通塊里，則輸出 "ok"（不含引號） 否則操作非法，不進行操作并輸出 "failed"（不含引號）。 ? 現(xiàn)在你來負責搞定這個問題吧。。。

輸入

第一行兩個用空格隔開的正整數(shù)?n,m?表示一共有?n?個結點，m?個操作。 接下來一行?n?個正整數(shù)，第?i?個正整數(shù)為?wi。 接下來?m?行，每行代表一個操作。

輸出

對于每個操作，輸出相應的結果。

輸入示例

11?23 10?5?11?7?8?14?30?3?16?20?19 link?1?2?5 link?2?3?3 link?3?4?7 link?4?5?8 link?2?6?10 link?6?7?15 link?4?7?3 link?6?8?9 link?6?8?6 link?7?9?12 link?9?11?10 link?7?10?4 link?9?10?8 query1?6?11 query1?2?10 query2?8?7 add1?8?5?100 query1?1?7 query2?8?7 add2?11?7?1000 query1?8?3 add2?3?2?2333 query1?1?5

輸出示例

ok ok ok ok ok ok ok ok ok ok ok ok ok -2?-2 5?73 16?85 ok 5?263 16?185 ok 1005?4233 ok 1011?9907

其他說明

1≤n≤50000,1≤m≤250000。 保證?link?和?cut?操作中的?w?滿足?1≤w≤10000，所以關于邊權的計算不會超出?32?位有符號整數(shù)范圍。 保證初始的?wi?不超過?109，保證所有?add1?和?add2?操作中的?d?之和不超過?109。 ---真心吐槽這道題應該是本OJ代碼長度最長的題呦→_→chx童鞋的極限縮行可是寫了612行呢。。。

?

題解：動態(tài)仙人掌哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

最棒的仙人掌講解看這里一共有四節(jié)：http://vfleaking.blog.163.com/blog/static/17480763420142176910962/

1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<queue> 6 #include<cstring> 7 #define PAU putchar(' ') 8 #define ENT putchar('\n') 9 #define MAXN 50005 10 #define MAXM 250005 11 #define is_NULL_tag(x) ((x)==0) 12 #define is_NULL_info(x) (x.size==0) 13 using namespace std; 14 inline int read(){ 15 int x=0,sig=1;char ch=getchar(); 16 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();} 17 while(isdigit(ch))x=10*x+ch-'0',ch=getchar(); 18 return x*=sig; 19 } 20 inline void write(int x){ 21 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x; 22 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10; 23 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return; 24 } 25 char ch; 26 inline void Pass_Pau(int x){while(x--) getchar();return;} 27 int n,Q; 28 struct Info{ 29 int mi,size; 30 long long sum; 31 }; 32 typedef int Tag; 33 const Tag NULL_TAG=0; 34 const Info NULL_INFO=(Info){2147483647,0,0}; 35 inline Info operator + (const Info &a,const Info &b){return (Info){std::min(a.mi,b.mi),a.size+b.size,a.sum+b.sum};} 36 inline Info operator * (const Info &a,const Tag &b){return a.size ? (Info){a.mi+b,a.size,a.sum+1LL*a.size*b}: a;} 37 struct splay_node{ 38 splay_node *s[2],*fa; 39 Info x,sum; 40 Tag tag,tag_sum; 41 inline void add_tag(Tag t){ 42 x=x*t;sum=sum*t; 43 tag=tag+t;tag_sum=tag_sum+t; 44 return; 45 } 46 inline void down(){ 47 if(is_NULL_tag(tag)) return; 48 if(s[0]) s[0]->add_tag(tag); 49 if(s[1]) s[1]->add_tag(tag); 50 tag=NULL_TAG; 51 return; 52 } 53 inline void update(){ 54 sum=x; 55 if(s[0]) sum=sum+s[0]->sum; 56 if(s[1]) sum=sum+s[1]->sum; 57 return; 58 } 59 }; 60 splay_node _splay[MAXN+MAXM]; 61 inline int get_parent(splay_node *x,splay_node *&fa){return (fa=x->fa) ? fa->s[1]==x : -1;} 62 inline void rotate(splay_node *x){ 63 splay_node *fa,*gfa; 64 int t1,t2; 65 t1=get_parent(x,fa); 66 t2=get_parent(fa,gfa); 67 if((fa->s[t1]=x->s[t1^1])) fa->s[t1]->fa=fa; 68 fa->fa=x;x->fa=gfa;x->s[t1^1]=fa; 69 if(t2!=-1) gfa->s[t2]=x; 70 fa->update(); 71 return; 72 } 73 inline void pushdown(splay_node *x){ 74 static splay_node *stack[MAXN+MAXM]; 75 int cnt=0; 76 while(x){ 77 stack[cnt++]=x; 78 x=x->fa; 79 } 80 while(cnt--) stack[cnt]->down(); 81 return; 82 } 83 inline splay_node * splay(splay_node *x){ 84 pushdown(x); 85 while(1){ 86 splay_node *fa,*gfa; 87 int t1,t2; 88 t1=get_parent(x,fa); 89 if(t1==-1) break; 90 t2=get_parent(fa,gfa); 91 if(t2==-1){ 92 rotate(x);break; 93 }else if(t1==t2){ 94 rotate(fa);rotate(x); 95 }else{ 96 rotate(x);rotate(x); 97 }; 98 } 99 x->update(); 100 return x; 101 } 102 inline splay_node * join(splay_node *a,splay_node *b){ 103 if(!a) return b; 104 if(!b) return a; 105 while(a->s[1]) a->down(),a=a->s[1]; 106 splay(a)->s[1]=b;b->fa=a; 107 a->update(); 108 return a; 109 } 110 struct lcc_node; 111 struct cycle{ 112 int A,B; 113 lcc_node *ex; 114 }; 115 struct lcc_node{ 116 lcc_node *s[2],*fa; 117 lcc_node *first,*last; 118 bool rev; 119 bool isedge; 120 bool mpath; 121 bool hasmpath; 122 bool mpathtag; 123 bool hasmpathtag; 124 bool hascyctag; 125 bool hascyc; 126 cycle *cyc; 127 cycle *cyctag; 128 int totlen; 129 int len; 130 int size; 131 Info x,sum,sub,ex,all; 132 Tag chain_tag,sub_tag,ex_tag_sum; 133 inline void add_rev_tag(){ 134 std::swap(s[0],s[1]); 135 std::swap(first,last); 136 rev^=1; 137 return; 138 } 139 inline void add_cyc_tag(cycle *c){ 140 if(isedge) cyc=c; 141 cyctag=c; 142 hascyctag=1; 143 hascyc=c; 144 return; 145 } 146 inline void add_mpath_tag(bool t){ 147 mpathtag=t; 148 hasmpathtag=1; 149 mpath=t&isedge; 150 hasmpath=t&(isedge|(size>1)); 151 return; 152 } 153 inline void add_chain_tag(Tag t) 154 { 155 if(is_NULL_tag(t)) return; 156 x=x*t;sum=sum*t; 157 chain_tag=chain_tag+t; 158 all=sum+sub; 159 return; 160 }; 161 inline void add_sub_tag(Tag t); 162 inline void down(){ 163 if(rev){ 164 if(s[0]) s[0]->add_rev_tag(); 165 if(s[1]) s[1]->add_rev_tag(); 166 rev=0; 167 } 168 if(hascyctag){ 169 if(s[0]) s[0]->add_cyc_tag(cyctag); 170 if(s[1]) s[1]->add_cyc_tag(cyctag); 171 hascyctag=0; 172 } 173 if(hasmpathtag){ 174 if(s[0]) s[0]->add_mpath_tag(mpathtag); 175 if(s[1]) s[1]->add_mpath_tag(mpathtag); 176 hasmpathtag=0; 177 } 178 if(!is_NULL_tag(chain_tag)){ 179 if(s[0]) s[0]->add_chain_tag(chain_tag); 180 if(s[1]) s[1]->add_chain_tag(chain_tag); 181 chain_tag=NULL_TAG; 182 } 183 if(!is_NULL_tag(sub_tag)){ 184 if(s[0]) s[0]->add_sub_tag(sub_tag); 185 if(s[1]) s[1]->add_sub_tag(sub_tag); 186 sub_tag=NULL_TAG; 187 } 188 return; 189 } 190 inline void update(); 191 }; 192 lcc_node lcc[MAXN+MAXM]; 193 lcc_node *_node_tot; 194 splay_node *splay_root[MAXN+MAXM]; 195 inline void lcc_node::add_sub_tag(Tag t){ 196 if(is_NULL_tag(t)) return; 197 sub=sub*t;ex=ex*t; 198 sub_tag=sub_tag+t; 199 ex_tag_sum=ex_tag_sum+t; 200 all=sum+sub; 201 // add tag to splay_root 202 int id=this-lcc; 203 if(splay_root[id]){ 204 splay_root[id]->add_tag(t); 205 } 206 } 207 inline void lcc_node::update(){ 208 totlen=len; 209 hascyc=cyc; 210 size=1; 211 hasmpath=mpath; 212 if(s[0]) totlen+=s[0]->totlen,hascyc|=s[0]->hascyc,size+=s[0]->size,hasmpath|=s[0]->hasmpath; 213 if(s[1]) totlen+=s[1]->totlen,hascyc|=s[1]->hascyc,size+=s[1]->size,hasmpath|=s[1]->hasmpath; 214 first=s[0]?s[0]->first:this; 215 last=s[1]?s[1]->last:this; 216 bool s0=s[0],s1=s[1]; 217 if(isedge){ 218 if(is_NULL_info(ex)){ 219 if(s0 && s1){ 220 sum=s[0]->sum+s[1]->sum; 221 sub=s[0]->sub+s[1]->sub; 222 }else if(s0){ 223 sum=s[0]->sum; 224 sub=s[0]->sub; 225 }else if(s[1]){ 226 sum=s[1]->sum; 227 sub=s[1]->sub; 228 }else{ 229 sub=sum=NULL_INFO; 230 } 231 }else{ 232 if(s0 && s1){ 233 sum=s[0]->sum+s[1]->sum; 234 sub=s[0]->sub+s[1]->sub+ex; 235 }else if(s0){ 236 sum=s[0]->sum; 237 sub=s[0]->sub+ex; 238 }else if(s[1]){ 239 sum=s[1]->sum; 240 sub=s[1]->sub+ex; 241 }else{ 242 sum=NULL_INFO; 243 sub=ex; 244 } 245 } 246 }else{ 247 splay_node *root=splay_root[this-lcc]; 248 if(root){ 249 if(s0 && s1){ 250 sum=s[0]->sum+s[1]->sum+x; 251 sub=s[0]->sub+s[1]->sub+root->sum; 252 }else if(s0){ 253 sum=s[0]->sum+x; 254 sub=s[0]->sub+root->sum; 255 }else if(s[1]){ 256 sum=s[1]->sum+x; 257 sub=s[1]->sub+root->sum; 258 }else{ 259 sub=root->sum; 260 sum=x; 261 } 262 }else{ 263 if(s0 && s1){ 264 sum=s[0]->sum+s[1]->sum+x; 265 sub=s[0]->sub+s[1]->sub; 266 }else if(s0){ 267 sum=s[0]->sum+x; 268 sub=s[0]->sub; 269 }else if(s[1]){ 270 sum=s[1]->sum+x; 271 sub=s[1]->sub; 272 }else{ 273 sum=x; 274 sub=NULL_INFO; 275 } 276 } 277 } 278 all=sum+sub; 279 return; 280 }; 281 inline lcc_node * new_edge_node(int u,int v,int len){ 282 lcc_node *ret=++_node_tot; 283 ret->s[0]=ret->s[1]=ret->fa=NULL; 284 ret->first=ret->last=ret; 285 ret->rev=0; 286 ret->isedge=1; 287 ret->hascyctag=ret->hascyc=0; 288 ret->cyc=ret->cyctag=NULL; 289 ret->totlen=ret->len=len; 290 ret->size=1; 291 ret->x=ret->sum=ret->sub=ret->ex=ret->all=NULL_INFO; 292 ret->chain_tag=ret->sub_tag=ret->ex_tag_sum=NULL_TAG; 293 return ret; 294 } 295 inline int get_parent(lcc_node *x,lcc_node *&fa){return (fa=x->fa) ? fa->s[0]==x?0:fa->s[1]==x?1:-1 : -1;} 296 inline void rotate(lcc_node *x){ 297 int t1,t2; 298 lcc_node *fa,*gfa; 299 t1=get_parent(x,fa); 300 t2=get_parent(fa,gfa); 301 if((fa->s[t1]=x->s[t1^1])) fa->s[t1]->fa=fa; 302 fa->fa=x;x->fa=gfa;x->s[t1^1]=fa; 303 if(t2!=-1) gfa->s[t2]=x; 304 fa->update(); 305 return; 306 } 307 inline void pushdown(lcc_node *x){ 308 static lcc_node *stack[MAXN+MAXM]; 309 int cnt=0; 310 while(1){ 311 stack[cnt++]=x; 312 lcc_node *fa=x->fa; 313 if(!fa || (fa->s[0]!=x && fa->s[1]!=x)) break; 314 x=fa; 315 } 316 while(cnt--) stack[cnt]->down(); 317 return; 318 } 319 inline lcc_node * splay(lcc_node *x){ 320 pushdown(x); 321 while(1){ 322 int t1,t2; 323 lcc_node *fa,*gfa; 324 t1=get_parent(x,fa); 325 if(t1==-1) break; 326 t2=get_parent(fa,gfa); 327 if(t2==-1){ 328 rotate(x);break; 329 }else if(t1==t2){ 330 rotate(fa);rotate(x); 331 }else{ 332 rotate(x);rotate(x); 333 } 334 } 335 x->update(); 336 return x; 337 } 338 inline int getrank(lcc_node *x){ 339 splay(x); 340 return 1+(x->s[0]?x->s[0]->size:0); 341 } 342 bool _attached[MAXN+MAXM]; 343 inline void detach_rch(lcc_node *x){ 344 if(!x->s[1]) return; 345 int X=x-lcc; 346 int id=x->s[1]->first-lcc; 347 _attached[id]=1; 348 splay_node *p=_splay+id; 349 p->s[0]=splay_root[X]; 350 if(splay_root[X]) splay_root[X]->fa=p; 351 p->s[1]=p->fa=NULL; 352 p->x=x->s[1]->all; 353 p->tag=p->tag_sum=NULL_TAG; 354 p->update(); 355 splay_root[X]=p; 356 x->s[1]=NULL; 357 return; 358 } 359 inline void attach_rch(lcc_node *x,lcc_node *y,int id){ 360 int X=x-lcc; 361 _attached[id]=0; 362 splay_node *p=_splay+id; 363 splay(p); 364 if(p->s[0]) p->s[0]->fa=NULL; 365 if(p->s[1]) p->s[1]->fa=NULL; 366 splay_root[X]=join(p->s[0],p->s[1]); 367 y->add_chain_tag(p->tag_sum); 368 y->add_sub_tag(p->tag_sum); 369 x->s[1]=y; 370 return; 371 } 372 inline void attach_rch(lcc_node *x,lcc_node *y,int id,int id2){ 373 if(_attached[id]) attach_rch(x,y,id); 374 else attach_rch(x,y,id2); 375 return; 376 } 377 inline void attach_rch(lcc_node *x,lcc_node *y){ 378 if(!y) return; 379 attach_rch(x,y,y->first-lcc); 380 return; 381 } 382 inline lcc_node * access(lcc_node *x){ 383 lcc_node *ret=NULL; 384 int last_ex_last_id; 385 while(x){ 386 lcc_node *t=splay(x)->s[0]; 387 if(!t){ 388 detach_rch(x); 389 if(ret) attach_rch(x,ret,ret->first-lcc,last_ex_last_id); 390 ret=x;x->update(); 391 x=x->fa; 392 continue; 393 } 394 while(t->s[1]) t->down(),t=t->s[1]; 395 if(!splay(t)->cyc){ 396 splay(x); 397 detach_rch(x); 398 if(ret) attach_rch(x,ret,ret->first-lcc,last_ex_last_id); 399 ret=x;x->update(); 400 x=x->fa; 401 continue; 402 } 403 cycle *c=t->cyc; 404 lcc_node *A=lcc+c->A,*B=lcc+c->B,*ex=splay(c->ex); 405 bool need_tag_down=false; 406 lcc_node *B_ex; 407 if(splay(B)->fa==A){ 408 detach_rch(B); 409 B->s[1]=ex;ex->fa=B;B->update(); 410 need_tag_down=true; 411 B_ex=B->s[0]->first; 412 }else if(splay(A)->fa==B){ 413 std::swap(c->A,c->B);std::swap(A,B);ex->add_rev_tag(); 414 detach_rch(B); 415 B->s[1]=ex;ex->fa=B;B->update(); 416 need_tag_down=true; 417 B_ex=B->s[0]->last; 418 }else{ 419 bool f=0; 420 if(getrank(A)>getrank(B)){ 421 std::swap(c->A,c->B);std::swap(A,B);ex->add_rev_tag(); 422 f=1; 423 } 424 splay(A)->s[1]->fa=NULL;A->s[1]=NULL;A->update(); 425 splay(B);detach_rch(B); 426 B->s[1]=ex;ex->fa=B;B->update(); 427 B_ex=f ? B->s[0]->last : B->s[0]->first; 428 } 429 // add tag to ex 430 Tag tag_ex=splay(B_ex)->ex_tag_sum; 431 B_ex->ex=NULL_INFO; 432 B_ex->update(); 433 ex=splay(B)->s[1]; 434 ex->add_chain_tag(tag_ex); 435 ex->add_sub_tag(tag_ex); 436 B->update(); 437 splay(x);c->B=x-lcc; 438 if(x->s[1]->totlen<x->s[0]->totlen) x->add_rev_tag(); 439 x->add_mpath_tag(x->s[1]->totlen==x->s[0]->totlen); 440 x->down(); 441 c->ex=x->s[1];x->s[1]->fa=NULL; 442 x->s[1]=NULL; 443 x->update(); 444 lcc_node *tmp=splay(x->first); 445 tmp->ex=c->ex->all; 446 tmp->ex_tag_sum=NULL_TAG; 447 tmp->update(); 448 splay(x); 449 if(ret) attach_rch(x,ret,ret->first-lcc,last_ex_last_id); 450 x->update(); 451 last_ex_last_id=c->ex->last-lcc; 452 if(splay(A)->s[1]) ret=x,x=x->fa; 453 else{ 454 if(need_tag_down) attach_rch(A,x,c->ex->last-lcc,x->first-lcc); 455 A->s[1]=x;x->fa=A;A->update(); 456 ret=A;x=A->fa; 457 } 458 } 459 return ret; 460 } 461 inline void setroot(int x){access(lcc+x)->add_rev_tag();}; 462 inline bool link(int u,int v,int len){ 463 if(u==v) return false; 464 setroot(u); 465 lcc_node *t=access(lcc+v); 466 while(t->s[0]) t->down(),t=t->s[0]; 467 if(splay(t)!=lcc+u){ 468 lcc_node *p=new_edge_node(u,v,len); 469 p->fa=splay(lcc+u); 470 lcc[u].s[0]=p; 471 lcc[u].fa=lcc+v; 472 lcc[u].update(); 473 splay(lcc+v)->s[1]=lcc+u; 474 lcc[v].update(); 475 return true; 476 } 477 if(t->hascyc) return false; 478 lcc_node *ex=new_edge_node(u,v,len); 479 cycle *c=new cycle((cycle){u,v,ex}); 480 ex->add_cyc_tag(c); 481 t->add_cyc_tag(c); 482 access(lcc+v); 483 return true; 484 } 485 inline bool cut(int u,int v,int len){ 486 if(u==v) return false; 487 setroot(u); 488 lcc_node *t=access(lcc+v); 489 while(t->s[0]) t->down(),t=t->s[0]; 490 if(splay(t)!=lcc+u) return false; 491 if(!t->hascyc){ 492 if(t->size!=3) return false; 493 if(t->totlen!=len) return false; 494 t=t->s[1]; 495 if(t->s[0]) t->down(),t=t->s[0]; 496 splay(t); 497 t->s[0]->fa=NULL;t->s[1]->fa=NULL; 498 return true; 499 } 500 t=splay(lcc+v)->s[0]; 501 while(t->s[1]) t->down(),t=t->s[1]; 502 cycle *c=splay(t)->cyc; 503 if(!c) return false; 504 t=splay(lcc+u)->s[1]; 505 while(t->s[0]) t->down(),t=t->s[0]; 506 if(splay(t)->cyc!=c) return false; 507 lcc_node *ex=c->ex; 508 if(ex->size==1 && ex->len==len){ 509 t->add_cyc_tag(NULL); 510 t->add_mpath_tag(0); 511 delete c; 512 return true; 513 } 514 if(t->size!=3 || t->len!=len) return false; 515 // lcc[u].mpath == 0 ! 516 ex->add_cyc_tag(NULL); 517 ex->add_mpath_tag(0); 518 ex->add_rev_tag(); 519 ex->add_sub_tag(t->ex_tag_sum); 520 ex->add_chain_tag(t->ex_tag_sum); 521 lcc[u].fa=lcc[v].fa=NULL; 522 while(ex->s[0]) ex->down(),ex=ex->s[0]; 523 splay(ex)->s[0]=lcc+u;lcc[u].fa=ex;ex->update(); 524 while(ex->s[1]) ex->down(),ex=ex->s[1]; 525 splay(ex)->s[1]=lcc+v;lcc[v].fa=ex;ex->update(); 526 delete c; 527 return true; 528 } 529 inline Info query_path(int u,int v){ 530 setroot(u); 531 lcc_node *t=access(lcc+v); 532 while(t->s[0]) t->down(),t=t->s[0]; 533 if(splay(t)!=lcc+u) return (Info){-1,-1,-1}; 534 if(t->hasmpath) return (Info){-2,-2,-2}; 535 return t->sum; 536 } 537 inline Info query_subcactus(int u,int v){ 538 setroot(u); 539 lcc_node *t=access(lcc+v); 540 while(t->s[0]) t->down(),t=t->s[0]; 541 if(splay(t)!=lcc+u) return (Info){-1,-1,-1}; 542 Info ret=splay(lcc+v)->x; 543 if(splay_root[v]) ret=ret+splay_root[v]->sum; 544 return ret; 545 } 546 inline bool modify_path(int u,int v,Tag tag){ 547 setroot(u); 548 lcc_node *t=access(lcc+v); 549 while(t->s[0]) t->down(),t=t->s[0]; 550 if(splay(t)!=lcc+u) return false; 551 if(t->hasmpath) return false; 552 t->add_chain_tag(tag); 553 return true; 554 } 555 inline bool modify_subcactus(int u,int v,Tag tag){ 556 setroot(u); 557 lcc_node *t=access(lcc+v); 558 while(t->s[0]) t->down(),t=t->s[0]; 559 if(splay(t)!=lcc+u) return false; 560 splay(lcc+v); 561 lcc[v].x=lcc[v].x*tag; 562 if(splay_root[v]) splay_root[v]->add_tag(tag); 563 lcc[v].update(); 564 return true; 565 } 566 void init(){ 567 n=read();Q=read(); 568 int i; 569 static int w[MAXN]; 570 for(i=1;i<=n;i++){ 571 w[i]=read(); 572 lcc[i].first=lcc[i].last=lcc+i; 573 lcc[i].size=1; 574 lcc[i].x=lcc[i].sum=lcc[i].all=(Info){w[i],1,w[i]}; 575 lcc[i].sub=lcc[i].ex=NULL_INFO; 576 lcc[i].chain_tag=lcc[i].sub_tag=lcc[i].ex_tag_sum=NULL_TAG; 577 } 578 _node_tot=lcc+n; 579 return; 580 } 581 void work(){ 582 for(int i=1;i<=Q;i++){ 583 char ch=getchar(); 584 while(ch<=32) ch=getchar(); 585 if(ch=='l'){ 586 Pass_Pau(3); 587 int u=read(),v=read(),len=read(); 588 puts(link(u,v,len) ? "ok" : "failed"); 589 }else if(ch=='c'){ 590 Pass_Pau(2); 591 int u=read(),v=read(),len=read(); 592 puts(cut(u,v,len) ? "ok" : "failed"); 593 }else if(ch=='q'){ 594 Pass_Pau(4); 595 ch=getchar(); 596 int u=read(),v=read(); 597 Info ret; 598 ret=ch=='1' ? query_path(u,v) : query_subcactus(u,v); 599 printf("%d %lld\n",ret.mi,ret.sum); 600 }else if(ch=='a'){ 601 Pass_Pau(2); 602 ch=getchar(); 603 int u=read(),v=read(),val=read(); 604 puts((ch=='1'?modify_path(u,v,val):modify_subcactus(u,v,val)) ? "ok" : "failed"); 605 }else puts("error"); 606 } 607 return; 608 } 609 void print(){ 610 return; 611 } 612 int main(){init();work();print();return 0;}

?

轉(zhuǎn)載于:https://www.cnblogs.com/chxer/p/4483282.html

總結

以上是生活随笔為你收集整理的COJ 0650 绝世难题（一） 可爱的仙人掌的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。