传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=620
| 绝世难题（一） 可爱的仙人掌 |
| 难度级别：E； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
---“神犇是怎么样的。。。” ---“神犇就是这种**题拿过来半小时随便A。。。(๑•̀ㅂ•́)و✧” 绝世难题之可爱的仙人掌
-------------------------我是题目和吐槽的分割线-------------------------
chx童鞋最近迷上了图论中的环，结果有一天他做梦都梦见了环。。。（¯﹃¯） ---“你最近一直研究我啊那你知道我有什么小名嘛？(,,• ₃ •,,)” ---“噗。。。我怎么知道你告诉我呗。。。Σ( ° △ °|||)︴” ---“其实嘛，我的小名叫做仙人掌了啊~” 噗。。。chx脑中不禁脑补了一下。。。(ㆀ˘･з･˘)
噗噗噗。。。chx心想好吧你说是就算是吧(⊙ ▽ ⊙) ---“其实呢，在一个无向连通图中呢，如果每一条边都只属于一个简单环，我们就把这个图叫做仙人掌。。。如果图中每一个连通块都是一个萌萌哒仙人掌且没有自环，那么我们就把这个图称作是沙漠。。。”
呵呵。。。好吧真的 好好好形象啊！！！(๑•̀ㅂ•́)و✧ 如果一个无向图的每个连通块都是个仙人掌，且不存在自环，我们就称之为沙漠。 现在呢，为了证明你是玩转仙人掌的神犇，chx给你 n 个结点，从 1 到 n 标号。 初始时没有任何边，且每个结点 i 有个权值 wi (wi>0) 。每次进行如下操作之一： link v uw：在结点 v,u 间连一条权值为 w 的边。 1≤v,u≤n 且 w 为正整数。 如果连边完成后图仍为沙漠，则输出 "ok"（不含引号）。 否则操作非法，撤销此次操作并输出 "failed"（不含引号）。 cut v uw：在结点 v,u 间删掉一条权值为 w 的边。 1≤v,u≤n 且 w 为正整数。 如果存在这样的边则输出 "ok"（不含引号）（如果有多条权值为 w 的边删去任意一条）。 否则操作非法，不进行操作并输出 "failed"（不含引号）。 query1 vu：查询结点 v 到结点 u 的最短路信息。 1≤v,u≤n。 输出两个用空格隔开的整数 min,σ，分别代表最短路上点权的最小值、和。 如果没有路可到达则 min=−1,σ=−1。 如果最短路不唯一则 min=−2,σ=−2。 query2 vu：查询以结点 v 为根，子仙人掌 u 的信息。 1≤v,u≤n。 以结点 v 为根，子仙人掌 u 的定义是，删掉v 到 u 之间的所有简单路径上的边之后，u 所在的连通块。 输出两个用空格隔开的整数 min,σ，分别代表子仙人掌 u 中点权的最小值、和。 如果 v,u 不连通则 min=−1,σ=−1。 add1 v ud：把结点 v 到结点 u 的最短路上的每一个结点的权值都加上 d。 1≤v,u≤n 且 d 为正整数。 如果有路可到达且最短路唯一，则输出 "ok"（不含引号） 否则操作非法，不进行操作并输出 "failed"（不含引号）。 add2 v ud：把以结点 v 为根，子仙人掌 u 的每一个结点的权值都加上 d。 1≤v,u≤n 且 d 为正整数。 如果 v,u 在同一个连通块里，则输出 "ok"（不含引号） 否则操作非法，不进行操作并输出 "failed"（不含引号）。 现在你来负责搞定这个问题吧。。。 |
|
输入
|
|
第一行两个用空格隔开的正整数 n,m 表示一共有 n 个结点，m 个操作。
接下来一行 n 个正整数，第 i 个正整数为 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 位有符号整数范围。 保证初始的 wi 不超过 109，保证所有 add1 和 add2 操作中的 d 之和不超过 109。 ---真心吐槽这道题应该是本OJ代码长度最长的题呦→_→chx童鞋的极限缩行可是写了612行呢。。。 |
题解：动态仙人掌哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
最棒的仙人掌讲解看这里一共有四节：http://vfleaking.blog.163.com/blog/static/17480763420142176910962/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define MAXN 50005
#define MAXM 250005
#define is_NULL_tag(x) ((x)==0)
#define is_NULL_info(x) (x.size==0)
using namespace std;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}
while(isdigit(ch))x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;
int len=,buf[];while(x)buf[len++]=x%,x/=;
for(int i=len-;i>=;i--)putchar(buf[i]+'');return;
}
char ch;
inline void Pass_Pau(int x){while(x--) getchar();return;}
int n,Q;
struct Info{
int mi,size;
long long sum;
};
typedef int Tag;
const Tag NULL_TAG=;
const Info NULL_INFO=(Info){,,};
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};}
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;}
struct splay_node{
splay_node *s[],*fa;
Info x,sum;
Tag tag,tag_sum;
inline void add_tag(Tag t){
x=x*t;sum=sum*t;
tag=tag+t;tag_sum=tag_sum+t;
return;
}
inline void down(){
if(is_NULL_tag(tag)) return;
if(s[]) s[]->add_tag(tag);
if(s[]) s[]->add_tag(tag);
tag=NULL_TAG;
return;
}
inline void update(){
sum=x;
if(s[]) sum=sum+s[]->sum;
if(s[]) sum=sum+s[]->sum;
return;
}
};
splay_node _splay[MAXN+MAXM];
inline int get_parent(splay_node *x,splay_node *&fa){return (fa=x->fa) ? fa->s[]==x : -;}
inline void rotate(splay_node *x){
splay_node *fa,*gfa;
int t1,t2;
t1=get_parent(x,fa);
t2=get_parent(fa,gfa);
if((fa->s[t1]=x->s[t1^])) fa->s[t1]->fa=fa;
fa->fa=x;x->fa=gfa;x->s[t1^]=fa;
if(t2!=-) gfa->s[t2]=x;
fa->update();
return;
}
inline void pushdown(splay_node *x){
static splay_node *stack[MAXN+MAXM];
int cnt=;
while(x){
stack[cnt++]=x;
x=x->fa;
}
while(cnt--) stack[cnt]->down();
return;
}
inline splay_node * splay(splay_node *x){
pushdown(x);
while(){
splay_node *fa,*gfa;
int t1,t2;
t1=get_parent(x,fa);
if(t1==-) break;
t2=get_parent(fa,gfa);
if(t2==-){
rotate(x);break;
}else if(t1==t2){
rotate(fa);rotate(x);
}else{
rotate(x);rotate(x);
};
}
x->update();
return x;
}
inline splay_node * join(splay_node *a,splay_node *b){
if(!a) return b;
if(!b) return a;
while(a->s[]) a->down(),a=a->s[];
splay(a)->s[]=b;b->fa=a;
a->update();
return a;
}
struct lcc_node;
struct cycle{
int A,B;
lcc_node *ex;
};
struct lcc_node{
lcc_node *s[],*fa;
lcc_node *first,*last;
bool rev;
bool isedge;
bool mpath;
bool hasmpath;
bool mpathtag;
bool hasmpathtag;
bool hascyctag;
bool hascyc;
cycle *cyc;
cycle *cyctag;
int totlen;
int len;
int size;
Info x,sum,sub,ex,all;
Tag chain_tag,sub_tag,ex_tag_sum;
inline void add_rev_tag(){
std::swap(s[],s[]);
std::swap(first,last);
rev^=;
return;
}
inline void add_cyc_tag(cycle *c){
if(isedge) cyc=c;
cyctag=c;
hascyctag=;
hascyc=c;
return;
}
inline void add_mpath_tag(bool t){
mpathtag=t;
hasmpathtag=;
mpath=t&isedge;
hasmpath=t&(isedge|(size>));
return;
}
inline void add_chain_tag(Tag t)
{
if(is_NULL_tag(t)) return;
x=x*t;sum=sum*t;
chain_tag=chain_tag+t;
all=sum+sub;
return;
};
inline void add_sub_tag(Tag t);
inline void down(){
if(rev){
if(s[]) s[]->add_rev_tag();
if(s[]) s[]->add_rev_tag();
rev=;
}
if(hascyctag){
if(s[]) s[]->add_cyc_tag(cyctag);
if(s[]) s[]->add_cyc_tag(cyctag);
hascyctag=;
}
if(hasmpathtag){
if(s[]) s[]->add_mpath_tag(mpathtag);
if(s[]) s[]->add_mpath_tag(mpathtag);
hasmpathtag=;
}
if(!is_NULL_tag(chain_tag)){
if(s[]) s[]->add_chain_tag(chain_tag);
if(s[]) s[]->add_chain_tag(chain_tag);
chain_tag=NULL_TAG;
}
if(!is_NULL_tag(sub_tag)){
if(s[]) s[]->add_sub_tag(sub_tag);
if(s[]) s[]->add_sub_tag(sub_tag);
sub_tag=NULL_TAG;
}
return;
}
inline void update();
};
lcc_node lcc[MAXN+MAXM];
lcc_node *_node_tot;
splay_node *splay_root[MAXN+MAXM];
inline void lcc_node::add_sub_tag(Tag t){
if(is_NULL_tag(t)) return;
sub=sub*t;ex=ex*t;
sub_tag=sub_tag+t;
ex_tag_sum=ex_tag_sum+t;
all=sum+sub;
// add tag to splay_root
int id=this-lcc;
if(splay_root[id]){
splay_root[id]->add_tag(t);
}
}
inline void lcc_node::update(){
totlen=len;
hascyc=cyc;
size=;
hasmpath=mpath;
if(s[]) totlen+=s[]->totlen,hascyc|=s[]->hascyc,size+=s[]->size,hasmpath|=s[]->hasmpath;
if(s[]) totlen+=s[]->totlen,hascyc|=s[]->hascyc,size+=s[]->size,hasmpath|=s[]->hasmpath;
first=s[]?s[]->first:this;
last=s[]?s[]->last:this;
bool s0=s[],s1=s[];
if(isedge){
if(is_NULL_info(ex)){
if(s0 && s1){
sum=s[]->sum+s[]->sum;
sub=s[]->sub+s[]->sub;
}else if(s0){
sum=s[]->sum;
sub=s[]->sub;
}else if(s[]){
sum=s[]->sum;
sub=s[]->sub;
}else{
sub=sum=NULL_INFO;
}
}else{
if(s0 && s1){
sum=s[]->sum+s[]->sum;
sub=s[]->sub+s[]->sub+ex;
}else if(s0){
sum=s[]->sum;
sub=s[]->sub+ex;
}else if(s[]){
sum=s[]->sum;
sub=s[]->sub+ex;
}else{
sum=NULL_INFO;
sub=ex;
}
}
}else{
splay_node *root=splay_root[this-lcc];
if(root){
if(s0 && s1){
sum=s[]->sum+s[]->sum+x;
sub=s[]->sub+s[]->sub+root->sum;
}else if(s0){
sum=s[]->sum+x;
sub=s[]->sub+root->sum;
}else if(s[]){
sum=s[]->sum+x;
sub=s[]->sub+root->sum;
}else{
sub=root->sum;
sum=x;
}
}else{
if(s0 && s1){
sum=s[]->sum+s[]->sum+x;
sub=s[]->sub+s[]->sub;
}else if(s0){
sum=s[]->sum+x;
sub=s[]->sub;
}else if(s[]){
sum=s[]->sum+x;
sub=s[]->sub;
}else{
sum=x;
sub=NULL_INFO;
}
}
}
all=sum+sub;
return;
};
inline lcc_node * new_edge_node(int u,int v,int len){
lcc_node *ret=++_node_tot;
ret->s[]=ret->s[]=ret->fa=NULL;
ret->first=ret->last=ret;
ret->rev=;
ret->isedge=;
ret->hascyctag=ret->hascyc=;
ret->cyc=ret->cyctag=NULL;
ret->totlen=ret->len=len;
ret->size=;
ret->x=ret->sum=ret->sub=ret->ex=ret->all=NULL_INFO;
ret->chain_tag=ret->sub_tag=ret->ex_tag_sum=NULL_TAG;
return ret;
}
inline int get_parent(lcc_node *x,lcc_node *&fa){return (fa=x->fa) ? fa->s[]==x?:fa->s[]==x?:- : -;}
inline void rotate(lcc_node *x){
int t1,t2;
lcc_node *fa,*gfa;
t1=get_parent(x,fa);
t2=get_parent(fa,gfa);
if((fa->s[t1]=x->s[t1^])) fa->s[t1]->fa=fa;
fa->fa=x;x->fa=gfa;x->s[t1^]=fa;
if(t2!=-) gfa->s[t2]=x;
fa->update();
return;
}
inline void pushdown(lcc_node *x){
static lcc_node *stack[MAXN+MAXM];
int cnt=;
while(){
stack[cnt++]=x;
lcc_node *fa=x->fa;
if(!fa || (fa->s[]!=x && fa->s[]!=x)) break;
x=fa;
}
while(cnt--) stack[cnt]->down();
return;
}
inline lcc_node * splay(lcc_node *x){
pushdown(x);
while(){
int t1,t2;
lcc_node *fa,*gfa;
t1=get_parent(x,fa);
if(t1==-) break;
t2=get_parent(fa,gfa);
if(t2==-){
rotate(x);break;
}else if(t1==t2){
rotate(fa);rotate(x);
}else{
rotate(x);rotate(x);
}
}
x->update();
return x;
}
inline int getrank(lcc_node *x){
splay(x);
return +(x->s[]?x->s[]->size:);
}
bool _attached[MAXN+MAXM];
inline void detach_rch(lcc_node *x){
if(!x->s[]) return;
int X=x-lcc;
int id=x->s[]->first-lcc;
_attached[id]=;
splay_node *p=_splay+id;
p->s[]=splay_root[X];
if(splay_root[X]) splay_root[X]->fa=p;
p->s[]=p->fa=NULL;
p->x=x->s[]->all;
p->tag=p->tag_sum=NULL_TAG;
p->update();
splay_root[X]=p;
x->s[]=NULL;
return;
}
inline void attach_rch(lcc_node *x,lcc_node *y,int id){
int X=x-lcc;
_attached[id]=;
splay_node *p=_splay+id;
splay(p);
if(p->s[]) p->s[]->fa=NULL;
if(p->s[]) p->s[]->fa=NULL;
splay_root[X]=join(p->s[],p->s[]);
y->add_chain_tag(p->tag_sum);
y->add_sub_tag(p->tag_sum);
x->s[]=y;
return;
}
inline void attach_rch(lcc_node *x,lcc_node *y,int id,int id2){
if(_attached[id]) attach_rch(x,y,id);
else attach_rch(x,y,id2);
return;
}
inline void attach_rch(lcc_node *x,lcc_node *y){
if(!y) return;
attach_rch(x,y,y->first-lcc);
return;
}
inline lcc_node * access(lcc_node *x){
lcc_node *ret=NULL;
int last_ex_last_id;
while(x){
lcc_node *t=splay(x)->s[];
if(!t){
detach_rch(x);
if(ret) attach_rch(x,ret,ret->first-lcc,last_ex_last_id);
ret=x;x->update();
x=x->fa;
continue;
}
while(t->s[]) t->down(),t=t->s[];
if(!splay(t)->cyc){
splay(x);
detach_rch(x);
if(ret) attach_rch(x,ret,ret->first-lcc,last_ex_last_id);
ret=x;x->update();
x=x->fa;
continue;
}
cycle *c=t->cyc;
lcc_node *A=lcc+c->A,*B=lcc+c->B,*ex=splay(c->ex);
bool need_tag_down=false;
lcc_node *B_ex;
if(splay(B)->fa==A){
detach_rch(B);
B->s[]=ex;ex->fa=B;B->update();
need_tag_down=true;
B_ex=B->s[]->first;
}else if(splay(A)->fa==B){
std::swap(c->A,c->B);std::swap(A,B);ex->add_rev_tag();
detach_rch(B);
B->s[]=ex;ex->fa=B;B->update();
need_tag_down=true;
B_ex=B->s[]->last;
}else{
bool f=;
if(getrank(A)>getrank(B)){
std::swap(c->A,c->B);std::swap(A,B);ex->add_rev_tag();
f=;
}
splay(A)->s[]->fa=NULL;A->s[]=NULL;A->update();
splay(B);detach_rch(B);
B->s[]=ex;ex->fa=B;B->update();
B_ex=f ? B->s[]->last : B->s[]->first;
}
// add tag to ex
Tag tag_ex=splay(B_ex)->ex_tag_sum;
B_ex->ex=NULL_INFO;
B_ex->update();
ex=splay(B)->s[];
ex->add_chain_tag(tag_ex);
ex->add_sub_tag(tag_ex);
B->update();
splay(x);c->B=x-lcc;
if(x->s[]->totlen<x->s[]->totlen) x->add_rev_tag();
x->add_mpath_tag(x->s[]->totlen==x->s[]->totlen);
x->down();
c->ex=x->s[];x->s[]->fa=NULL;
x->s[]=NULL;
x->update();
lcc_node *tmp=splay(x->first);
tmp->ex=c->ex->all;
tmp->ex_tag_sum=NULL_TAG;
tmp->update();
splay(x);
if(ret) attach_rch(x,ret,ret->first-lcc,last_ex_last_id);
x->update();
last_ex_last_id=c->ex->last-lcc;
if(splay(A)->s[]) ret=x,x=x->fa;
else{
if(need_tag_down) attach_rch(A,x,c->ex->last-lcc,x->first-lcc);
A->s[]=x;x->fa=A;A->update();
ret=A;x=A->fa;
}
}
return ret;
}
inline void setroot(int x){access(lcc+x)->add_rev_tag();};
inline bool link(int u,int v,int len){
if(u==v) return false;
setroot(u);
lcc_node *t=access(lcc+v);
while(t->s[]) t->down(),t=t->s[];
if(splay(t)!=lcc+u){
lcc_node *p=new_edge_node(u,v,len);
p->fa=splay(lcc+u);
lcc[u].s[]=p;
lcc[u].fa=lcc+v;
lcc[u].update();
splay(lcc+v)->s[]=lcc+u;
lcc[v].update();
return true;
}
if(t->hascyc) return false;
lcc_node *ex=new_edge_node(u,v,len);
cycle *c=new cycle((cycle){u,v,ex});
ex->add_cyc_tag(c);
t->add_cyc_tag(c);
access(lcc+v);
return true;
}
inline bool cut(int u,int v,int len){
if(u==v) return false;
setroot(u);
lcc_node *t=access(lcc+v);
while(t->s[]) t->down(),t=t->s[];
if(splay(t)!=lcc+u) return false;
if(!t->hascyc){
if(t->size!=) return false;
if(t->totlen!=len) return false;
t=t->s[];
if(t->s[]) t->down(),t=t->s[];
splay(t);
t->s[]->fa=NULL;t->s[]->fa=NULL;
return true;
}
t=splay(lcc+v)->s[];
while(t->s[]) t->down(),t=t->s[];
cycle *c=splay(t)->cyc;
if(!c) return false;
t=splay(lcc+u)->s[];
while(t->s[]) t->down(),t=t->s[];
if(splay(t)->cyc!=c) return false;
lcc_node *ex=c->ex;
if(ex->size== && ex->len==len){
t->add_cyc_tag(NULL);
t->add_mpath_tag();
delete c;
return true;
}
if(t->size!= || t->len!=len) return false;
// lcc[u].mpath == 0 !
ex->add_cyc_tag(NULL);
ex->add_mpath_tag();
ex->add_rev_tag();
ex->add_sub_tag(t->ex_tag_sum);
ex->add_chain_tag(t->ex_tag_sum);
lcc[u].fa=lcc[v].fa=NULL;
while(ex->s[]) ex->down(),ex=ex->s[];
splay(ex)->s[]=lcc+u;lcc[u].fa=ex;ex->update();
while(ex->s[]) ex->down(),ex=ex->s[];
splay(ex)->s[]=lcc+v;lcc[v].fa=ex;ex->update();
delete c;
return true;
}
inline Info query_path(int u,int v){
setroot(u);
lcc_node *t=access(lcc+v);
while(t->s[]) t->down(),t=t->s[];
if(splay(t)!=lcc+u) return (Info){-,-,-};
if(t->hasmpath) return (Info){-,-,-};
return t->sum;
}
inline Info query_subcactus(int u,int v){
setroot(u);
lcc_node *t=access(lcc+v);
while(t->s[]) t->down(),t=t->s[];
if(splay(t)!=lcc+u) return (Info){-,-,-};
Info ret=splay(lcc+v)->x;
if(splay_root[v]) ret=ret+splay_root[v]->sum;
return ret;
}
inline bool modify_path(int u,int v,Tag tag){
setroot(u);
lcc_node *t=access(lcc+v);
while(t->s[]) t->down(),t=t->s[];
if(splay(t)!=lcc+u) return false;
if(t->hasmpath) return false;
t->add_chain_tag(tag);
return true;
}
inline bool modify_subcactus(int u,int v,Tag tag){
setroot(u);
lcc_node *t=access(lcc+v);
while(t->s[]) t->down(),t=t->s[];
if(splay(t)!=lcc+u) return false;
splay(lcc+v);
lcc[v].x=lcc[v].x*tag;
if(splay_root[v]) splay_root[v]->add_tag(tag);
lcc[v].update();
return true;
}
void init(){
n=read();Q=read();
int i;
static int w[MAXN];
for(i=;i<=n;i++){
w[i]=read();
lcc[i].first=lcc[i].last=lcc+i;
lcc[i].size=;
lcc[i].x=lcc[i].sum=lcc[i].all=(Info){w[i],,w[i]};
lcc[i].sub=lcc[i].ex=NULL_INFO;
lcc[i].chain_tag=lcc[i].sub_tag=lcc[i].ex_tag_sum=NULL_TAG;
}
_node_tot=lcc+n;
return;
}
void work(){
for(int i=;i<=Q;i++){
char ch=getchar();
while(ch<=) ch=getchar();
if(ch=='l'){
Pass_Pau();
int u=read(),v=read(),len=read();
puts(link(u,v,len) ? "ok" : "failed");
}else if(ch=='c'){
Pass_Pau();
int u=read(),v=read(),len=read();
puts(cut(u,v,len) ? "ok" : "failed");
}else if(ch=='q'){
Pass_Pau();
ch=getchar();
int u=read(),v=read();
Info ret;
ret=ch=='' ? query_path(u,v) : query_subcactus(u,v);
printf("%d %lld\n",ret.mi,ret.sum);
}else if(ch=='a'){
Pass_Pau();
ch=getchar();
int u=read(),v=read(),val=read();
puts((ch==''?modify_path(u,v,val):modify_subcactus(u,v,val)) ? "ok" : "failed");
}else puts("error");
}
return;
}
void print(){
return;
}
int main(){init();work();print();return ;}