本文共 5759 字，大约阅读时间需要 19 分钟。
BZOJ卡不过灰常蛋疼（毕竟人蠢自带巨大常数
这和动态维护最小生成树很像，但加边变成了删边，似乎没法做了。
然后根据之前的套路离线做，删边变成加边，就可以做了orz
二分查找的：（慢
// It is made by XZZ#include #include #include #include #define il inline#define rg register#define vd void#define sta staticusing namespace std;il int gi(){ rg int x=0,f=1;rg char ch=getchar(); while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;}const int maxn=100001;stack stk;namespace LCT{ typedef const int& fast; int ch[maxn*2][2],fa[maxn*2],mx[maxn*2],w[maxn*2],index,A[maxn*2],B[maxn*2];bool rev[maxn*2]; il vd upd(fast x){ mx[x]=x; if(w[mx[ch[x][0]]]>w[mx[x]])mx[x]=mx[ch[x][0]]; if(w[mx[ch[x][1]]]>w[mx[x]])mx[x]=mx[ch[x][1]]; } il vd Rev(fast x){if(x)rev[x]^=1,swap(ch[x][0],ch[x][1]);} il vd down(fast x){if(rev[x])Rev(ch[x][0]),Rev(ch[x][1]),rev[x]=0;} il bool isrt(fast x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} il vd rotate(fast x){ sta int y,z,o;y=fa[x],z=fa[y],o=x==ch[y][1]; if(!isrt(y))ch[z][y==ch[z][1]]=x;fa[x]=z; ch[y][o]=ch[x][!o],fa[ch[x][!o]]=y; ch[x][!o]=y,fa[y]=x; upd(y); } il vd splay(fast x){ sta int y,z,stk[maxn],top;stk[top=1]=x; for(rg int i=x;!isrt(i);i=fa[i])stk[++top]=fa[i]; while(top)down(stk[top--]); for(y=fa[x],z=fa[y];!isrt(x);rotate(x),y=fa[x],z=fa[y]) if(!isrt(y))rotate(((x==ch[y][0])^(y==ch[z][0]))?y:x); upd(x); } il vd access(int x){for(rg int y=0;x;x=fa[y=x])splay(x),ch[x][1]=y,upd(x);} il vd makert(fast x){access(x),splay(x),Rev(x);} il vd link(fast x,fast y){makert(x),fa[x]=y;} il vd cut(fast x,fast y){makert(x),access(y),splay(y);fa[x]=ch[y][0]=0;} il int Query(fast x,fast y){makert(x),access(y),splay(y);return mx[y];} il int find(int x){access(x),splay(x);while(ch[x][0])x=ch[x][0];return x;} il vd Link(fast x,fast y,fast _w){ if(find(x)^find(y)){w[++index]=_w,link(A[index]=x,index),link(B[index]=y,index);return;} sta int z;z=Query(x,y); if(_w>=w[z])return; cut(A[z],z),cut(B[z],z); w[z]=_w,link(A[z]=x,z),link(B[z]=y,z); }};namespace GGMap{ struct gzy{int x,y,*k;}s[maxn]; il bool cmp(const gzy&a,const gzy&b){return a.x==b.x?a.y >1; if(s[mid].x Y[i])swap(X[i],Y[i]);} for(rg int i=1;i<=q;++i){ opt[i]=gi(),A[i]=gi(),B[i]=gi();if(A[i]>B[i])swap(A[i],B[i]); if(opt[i]==2)GGMap::insert(A[i],B[i],&C[i]); } GGMap::prepare(); for(rg int i=1;i<=m;++i){ int *it=GGMap::find(X[i],Y[i]); if(it==NULL)LCT::Link(X[i],Y[i],Z[i]); else *it=Z[i]; } while(q){ if(opt[q]==1)stk.push(LCT::w[LCT::Query(A[q],B[q])]); else LCT::Link(A[q],B[q],C[q]); --q; } while(!stk.empty())printf("%d\n",stk.top()),stk.pop(); return 0;}
map+一丁点哈希优化：（较上面快，但还是慢
// It is made by XZZ#include #include #include #include #define il inline#define rg register#define vd void#define sta staticusing namespace std;il int gi(){ rg int x=0,f=1;rg char ch=getchar(); while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f;}const int maxn=100001;map ,int>yyb[32768];stack stk;namespace LCT{ typedef const int& fast; int ch[maxn*2][2],fa[maxn*2],mx[maxn*2],w[maxn*2],index,A[maxn*2],B[maxn*2];bool rev[maxn*2]; il vd upd(fast x){ mx[x]=x; if(w[mx[ch[x][0]]]>w[mx[x]])mx[x]=mx[ch[x][0]]; if(w[mx[ch[x][1]]]>w[mx[x]])mx[x]=mx[ch[x][1]]; } il vd Rev(fast x){if(x)rev[x]^=1,swap(ch[x][0],ch[x][1]);} il vd down(fast x){if(rev[x])Rev(ch[x][0]),Rev(ch[x][1]),rev[x]=0;} il bool isrt(fast x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;} il vd rotate(fast x){ sta int y,z,o;y=fa[x],z=fa[y],o=x==ch[y][1]; if(!isrt(y))ch[z][y==ch[z][1]]=x;fa[x]=z; ch[y][o]=ch[x][!o],fa[ch[x][!o]]=y; ch[x][!o]=y,fa[y]=x; upd(y); } il vd splay(fast x){ sta int y,z,stk[maxn],top;stk[top=1]=x; for(rg int i=x;!isrt(i);i=fa[i])stk[++top]=fa[i]; while(top)down(stk[top--]); for(y=fa[x],z=fa[y];!isrt(x);rotate(x),y=fa[x],z=fa[y]) if(!isrt(y))rotate(((x==ch[y][0])^(y==ch[z][0]))?y:x); upd(x); } il vd access(int x){for(rg int y=0;x;x=fa[y=x])splay(x),ch[x][1]=y,upd(x);} il vd makert(fast x){access(x),splay(x),Rev(x);} il vd link(fast x,fast y){makert(x),fa[x]=y;} il vd cut(fast x,fast y){makert(x),access(y),splay(y);fa[x]=ch[y][0]=0;} il int Query(fast x,fast y){makert(x),access(y),splay(y);return mx[y];} il int find(int x){access(x),splay(x);while(ch[x][0])x=ch[x][0];return x;} il vd Link(fast x,fast y,fast _w){ if(find(x)^find(y)){w[++index]=_w,link(A[index]=x,index),link(B[index]=y,index);return;} sta int z;z=Query(x,y); if(_w>=w[z])return; cut(A[z],z),cut(B[z],z); w[z]=_w,link(A[z]=x,z),link(B[z]=y,z); }};int opt[maxn],A[maxn],B[maxn],C[maxn];int X[10000001],Y[10000001],Z[10000001];int main(){ freopen("tube_strong.in","r",stdin); freopen("tube_strong.out","w",stdout); int n=gi(),m=gi(),q=gi(),k; LCT::index=n; for(rg int i=1;i<=m;++i){X[i]=gi(),Y[i]=gi(),Z[i]=gi();if(X[i]>Y[i])swap(X[i],Y[i]);} for(rg int i=1;i<=q;++i){ opt[i]=gi(),A[i]=gi(),B[i]=gi();if(A[i]>B[i])swap(A[i],B[i]); if(opt[i]==2)yyb[(A[i]+B[i]*23333ll)&32767][make_pair(A[i],B[i])]=-1; } for(rg int i=1;i<=m;++i){ sta map ,int>::iterator it; k=(X[i]+Y[i]*23333ll)&32767; it=yyb[k].find(make_pair(X[i],Y[i])); if(it==yyb[k].end())LCT::Link(X[i],Y[i],Z[i]); else it->second=Z[i]; } while(q){ if(opt[q]==1)stk.push(LCT::w[LCT::Query(A[q],B[q])]); else LCT::Link(A[q],B[q],yyb[(A[q]+B[q]*23333ll)&32767][make_pair(A[q],B[q])]); --q; } while(!stk.empty())printf("%d\n",stk.top()),stk.pop(); return 0;}
//orz各位巨犇
转载于:https://www.cnblogs.com/xzz_233/p/8179411.html