[bzoj2594]-[WC2006]水管局长

发布于 2018-02-18  23 次阅读



题目(BZOJ)(数据加强)
题目(洛谷)(某种意义上也算数据加强)
...我可以说这是LCT裸题吗?
只需要离线操作,倒着加边就行了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <cctype>
#include <vector>
#include <climits>
#include <ext/pb_ds/assoc_container.hpp>
#define llmax LLONG_MAX
#define llmin LLONG_MIN
using namespace std;
using namespace __gnu_pbds;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=100050;
const int M=1500500;
int n,m,Q;
struct querys{
	int x,y,opt,ans;
	int id;
}q[N];
struct edge{
	int x,y,w;
	int id;
	bool del;
}e[M];
inline bool cmp1(const edge &x,const edge &y){
	if (x.x==y.x) return x.y<y.y;
	else return x.x<y.x;
}
inline bool cmp2(const edge &x,const edge &y){
	return x.w<y.w;
}
inline bool cmp3(const edge &x,const edge &y){
	return x.id<y.id;
}
int f[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline int findno(int x,int y){
	int l=1,r=m,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if (e[mid].x<x||(e[mid].x==x&&e[mid].y<y))l=mid+1;
		else if (e[mid].x==x&&e[mid].y==y)return mid;
		else r=mid-1;
	}
	return -1;
}
struct LCT{
	int a[M],mx[M],fa[M],que[M],ch[M][2],top;bool rev[M];
	inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
	inline void pushup(int x){
		int l=ch[x][0],r=ch[x][1];
		mx[x]=x;
		if(a[mx[l]]>a[mx[x]])mx[x]=mx[l];
		if(a[mx[r]]>a[mx[x]])mx[x]=mx[r];
	}
	inline void pushdown(int x){
		int l=ch[x][0],r=ch[x][1];
		if(rev[x]){
			rev[x]^=1;rev[l]^=1;rev[r]^=1;
			swap(ch[x][0],ch[x][1]);
		}
	}
	inline void roll(int x){
		int y=fa[x],z=fa[y],l,r;
		l=(ch[y][0]==x)^1;r=l^1;
		if(!isroot(y)){if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;}
		fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
		ch[y][l]=ch[x][r];ch[x][r]=y;
		pushup(y);pushup(x);
	}
	inline void splay(int x){
		que[top=1]=x;
		for(int i=x;!isroot(i);i=fa[i])que[++top]=fa[i];
		for(int i=top;i;--i)pushdown(que[i]);
		while(!isroot(x)){
			int y=fa[x],z=fa[y];
			if(!isroot(y)){if((ch[y][0]==x)^(ch[z][0]==x))roll(x);else roll(y);}roll(x);
		}
	}
	inline void access(int x){for(int i=0;x;i=x,x=fa[x])splay(x),ch[x][1]=i,pushup(x);}
	inline void makeroot(int x){access(x);splay(x);rev[x]^=1;}
	inline int find(int x){access(x);splay(x);while(ch[x][0])x=ch[x][0];return x;}
	inline void split(int x,int y){makeroot(x);access(y);splay(y);}
	inline void cut(int x,int y){split(x,y);if(ch[y][0]==x)ch[y][0]=0,fa[x]=0;}
	inline void link(int x,int y){makeroot(x);fa[x]=y;}
	inline int query(int x,int y){split(x,y);return mx[y];}
}lct;
int main(){
	read(n),read(m),read(Q);
	for (int i=1;i<=m;++i){
		int x,y,t;read(x),read(y),read(t);
		if(x>y)swap(x,y);
		e[i].x=x,e[i].y=y,e[i].w=t;
	}
	sort(e+1,e+m+1,cmp2);
	for (int i=1;i<=m;++i){
		e[i].id=i;
		lct.mx[n+i]=n+i;
		lct.a[n+i]=e[i].w;
	}
	sort(e+1,e+m+1,cmp1);
	for (int i=1;i<=Q;++i){
		read(q[i].opt),read(q[i].x),read(q[i].y);
		if (q[i].opt==2){
			if(q[i].x>q[i].y)swap(q[i].x,q[i].y);
			int t=findno(q[i].x,q[i].y);
			q[i].id=e[t].id;e[t].del=1;
		}
	}
	sort(e+1,e+m+1,cmp3);
	int cnt=0;
	for (int i=1;i<=n;++i) f[i]=i;
	for (int i=1;i<=m;++i){
		if (e[i].del) continue;
		int px=find(e[i].x),py=find(e[i].y);
		if(f[px]!=py){
			f[px]=py;
			lct.link(e[i].x,i+n);
			lct.link(e[i].y,i+n);
			++cnt;
			if(cnt==n-1)break;
		}
	}
	for (int i=Q;i;--i){
		if (q[i].opt==1){
			q[i].ans=lct.a[lct.query(q[i].x,q[i].y)];
			continue;
		}
		int x=q[i].x,y=q[i].y,k=q[i].id;
		int tmp=lct.query(x,y);
		if (e[k].w<lct.a[tmp]){
			lct.cut(e[tmp-n].x,tmp);lct.cut(e[tmp-n].y,tmp);
			lct.link(x,k+n);lct.link(y,k+n);
		}
	}
	for (int i=1;i<=Q;++i){
		if(q[i].opt==1)printf(
	}
	return 0;
}