[UOJ30/Codeforces Round #278 E]Tourists

传送门

好毒瘤的一道题QAQ，搞了好几好几天。

UOJ上卡在了53个点，CF上过了，懒得优化常数了

刚看时一眼Tarjan搞个强连通分量然后缩点树链剖分xjb搞搞就行了，然后写完了，然后WA了QAQ。

思考了一会把代码全删了，加了个mulutiset重写一遍，然后又是各种WA。

然后去看了POPOQQQ大爷的代码。原来把无向图缩成一个树用的是点双联通分量，搞不清图论的概念只能自扇脸..

然后去研究了点双联通分量，搞了一道题，顺便给Trajn搞了个小总结。

这道题其实就是缩点然后剖剖剖。但是我的姿势不太对，而且中间也有一些细节。

先点双缩成一颗树，然后对于每个点双新建一虚点，点双中的每个割点向虚点连边。这样最好形成的树的每一条路径就一定是虚点-割点-虚点-割点.....

剩下的任务是不是就是敲剖分的模板了？

并不是hhh。考虑修改操作，每次修改的如果非割点，更新这个点所在的点双就行了也就是树中的虚点。但是如果修改的点是割点的话，就需要更新这个割点所连接的每个点双，因为一个割点可以属于多个点双。如果出题人给你搞个菊花图你就GG了。

PS.对于修改操作，需要用STL里的$multiset$,代码如下：

struct BCC{
	int v;msi s;
	inline void insert(int num){s.insert(num);v=*s.begin();}
	inline void change(int x,int y){s.erase(s.find(x));s.insert(y);v=*s.begin();}
}bcc[MAXN];

换个思路，如果更新割点需要更新所连接的每个点双，那么在查询一个点双的时候是否可以顺便查询他的父亲（必为割点）？

所以在查询的时候，如果当前点是虚点，再查询一下父亲就OK了。

//UOJ 30 Fuck this problem
//by Cydiater
//2016.11.1
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctime>
#include <bitset>
#include <queue>
using namespace std;
#define ll long long
#define up(i,j,n)		for(int i=j;i<=n;i++)
#define down(i,j,n)		for(int i=j;i>=n;i--)
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define Auto(i,node)		for(int i=LINK[node];i;i=e[i].next)
#define msi multiset<int>
const int MAXN=2e5+5;
const int oo=0x3f3f3f3f;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int N,M,Q,Val[MAXN],stack[MAXN],top=0,dfn[MAXN],low[MAXN],dfs_clock=0,group[MAXN],group_num=0,fa[MAXN][25],dep[MAXN],son[MAXN],siz[MAXN],Pos[MAXN],Top[MAXN],val[MAXN],cnt=0;
int t[MAXN<<3],k,v,L,R,LEN=0;
bool iscut[MAXN];
char opt;
struct edge{int x,y,next;}u[MAXN<<1];
struct BCC{
	int v;msi s;
	inline void insert(int num){s.insert(num);v=*s.begin();}
	inline void change(int x,int y){s.erase(s.find(x));s.insert(y);v=*s.begin();}
}bcc[MAXN];
inline void Inserter(int x,int y){u[++LEN].x=x;u[LEN].y=y;}
struct Graph{
	int LINK[MAXN],len;
	edge e[MAXN<<2];
	inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;}
	inline void Insert(int x,int y){insert(x,y);insert(y,x);}
	void tarjan(int node){
		dfn[node]=low[node]=++dfs_clock;
		stack[++top]=node;
		Auto(i,node)if(!dfn[e[i].y]){
			tarjan(e[i].y);
			cmin(low[node],low[e[i].y]);
			if(low[e[i].y]>=dfn[node]){
				group_num++;int tmp;iscut[node]=1;
				do{
					tmp=stack[top--];
					group[tmp]=group_num;
					if(iscut[tmp])Inserter(tmp+N,group_num);
				}while(tmp!=e[i].y);
				Inserter(node+N,group_num);
			}
		}else cmin(low[node],dfn[e[i].y]);
	}
	void dfs1(int node,int deep,int father){
		dep[node]=deep;fa[node][0]=father;son[node]=0;
		int max_siz=0;siz[node]=1;
		Auto(i,node)if(e[i].y!=father){
			dfs1(e[i].y,deep+1,node);
			if(siz[e[i].y]>max_siz){
				max_siz=siz[e[i].y];
				son[node]=e[i].y;
			}
		}
	}
	void dfs2(int node,int tp){
		Top[node]=tp;Pos[node]=++cnt;val[cnt]=bcc[node].v;
		if(son[node])dfs2(son[node],tp);
		Auto(i,node)if(e[i].y!=fa[node][0]&&e[i].y!=son[node])
			dfs2(e[i].y,e[i].y);
	}
	int LCA(int x,int y){
		if(x==y)		return x;
		if(dep[x]<dep[y])swap(x,y);
		down(i,18,0)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
		if(x==y)		return x;
		down(i,18,0)if(fa[x][i]!=0&&fa[x][i]!=fa[y][i]){
			x=fa[x][i];y=fa[y][i];
		}
		return fa[x][0];
	}
}G1,G2;
namespace solution{
	inline void reload(int root){t[root]=min(t[root<<1],t[root<<1|1]);}
	void init(){
		N=read();M=read();Q=read();
		up(i,1,N)Val[i]=read();
		up(i,1,M){
			int x=read(),y=read();
			G1.Insert(x,y);
		}
	}
	void build(int leftt,int rightt,int root){
		if(leftt==rightt){t[root]=val[leftt];return;}
		int mid=(leftt+rightt)>>1;
		build(leftt,mid,root<<1);
		build(mid+1,rightt,root<<1|1);
		reload(root);
	}
	inline void updata(int leftt,int rightt,int root){
		if(leftt==rightt){
			t[root]=v;return;
		}
		int mid=(leftt+rightt)>>1;
		if(k>mid)updata(mid+1,rightt,root<<1|1);
		if(k<=mid)updata(leftt,mid,root<<1);
		reload(root);
	}
	inline int Get(int leftt,int rightt,int root){
		if(leftt>=L&&rightt<=R)	return t[root];
		int mid=(leftt+rightt)>>1;
		if(L>=mid+1)	return Get(mid+1,rightt,root<<1|1);
		else if(R<=mid)	return Get(leftt,mid,root<<1);
		else            return min(Get(leftt,mid,root<<1),Get(mid+1,rightt,root<<1|1));
	}
	inline int get(int node,int lca){
		int ans=oo;
		while(Top[node]!=Top[lca]){
			L=Pos[Top[node]];R=Pos[node];
			cmin(ans,Get(1,cnt,1));
			node=fa[Top[node]][0];
		}
		L=Pos[lca];R=Pos[node];
		cmin(ans,Get(1,cnt,1));
		return ans;
	}
	void get_ancestor(){
		up(i,1,20)up(node,1,N<<1)if(fa[node][i-1])
			fa[node][i]=fa[fa[node][i-1]][i-1];
	}
	void slove(){
		memset(iscut,0,sizeof(iscut));
		G1.tarjan(1);
		up(i,1,LEN){
			int x=u[i].x,y=u[i].y;
			G2.Insert(x,y);
		}
		up(i,1,N){
			if(i!=1)bcc[group[i]].insert(Val[i]);
			if(iscut[i])bcc[i+N].insert(oo);
		}
		G2.dfs1(N+1,0,0);G2.dfs2(N+1,N+1);
		build(1,cnt,1);get_ancestor();
		while(Q--){
			scanf("%c",&opt);
			if(opt=='C'){
				int x=read(),y=read();
				if(x!=1){
					bcc[group[x]].change(Val[x],y);
					k=Pos[group[x]];v=bcc[group[x]].v;
					updata(1,cnt,1);
				}
				Val[x]=y;
			}else{
				int x=read(),y=read();
				if(x==y){
					printf("%d\n",Val[x]);
					continue;
				}
				x=iscut[x]?x+N:group[x];
				y=iscut[y]?y+N:group[y];
				int lca=G2.LCA(x,y),ans=oo;
				if(lca<=group_num)lca=fa[lca][0];
				ans=Val[lca-N];
				cmin(ans,min(get(x,lca),get(y,lca)));
				printf("%d\n",ans);
			}
		}
	}
}
int main(){
	//freopen("input.in","r",stdin);
	using namespace solution;
	init();
	slove();
	return 0;
}

巴特西

[UOJ30/Codeforces Round #278 E]Tourists

最新文章

热门文章