洛谷P4768 [NOI2018]歸程（可持久化并查集，最短路）

閑話

一個蒟蒻，在網絡同步賽上進行了這樣的表演——

T2組合計數不會，T3字元串資料結構不會，于是爆肝T1

一開始以為整個地圖都有車，然後寫了2h+的樹套樹，終于發現樣例過不去

然後寫可持久化并查集Debug到13:20過了前4個樣例，然後第5個T飛了。

FST？

。。。。。。

FST！

完美收獲50分暴力分。

原來是按秩合并那裡咕咕了。

從50到100的蛻變，隻需一行，你值的擁有。

思路

不會kruscal重構樹

容易發現，假設我們确定了水位線，那麼就确定了圖中有哪些邊是連通的。這時候的答案該如何确定呢？因為車可以在一個連通塊裡随便開，是以同一個連通塊裡的點的答案都是一樣的，為連通塊内離\(1\)最近的點到\(1\)的距離。

那當然要首先把單源最短路求出來。SPFA死了？被固定了？（參考生物必修3），還好蒟蒻寫的是dijkstra。

因為并查集隻能合并，是以我們要按高度從大到小排序依次加邊。如果是離線那好辦了，把詢問也按高度排個序，每在并查集裡加一條邊就可以完成若幹個詢問。

那強制線上？當然要把合并過程中的每個版本都存起來啦！用可持久化并查集（蒟蒻之前寫過一篇blog）

當然，高度要離散化，為了讓每個詢問通過二分找到對應版本。

複雜度\(O(n\log m+(m+q)\log^2n)\)，當然這裡寫的有點醜，在倒序合并的過程中可以在外面放并查集，祖先到并查集裡跳，比在可持久化并查集裡跳快多了，複雜度\(O(n\log m+m\log n+q\log^2n)\)。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define UI unsigned int
#define RG register
#define I inline
#define R RG UI
#define G c=getchar()
using namespace std;
const int N=2e5+9,M=8e5+9,S=2e7;
struct NODE{
	UI u,d;
	I bool operator<(RG NODE x)const{return d>x.d;}
};//堆優化dijkstra的節點
struct EDGE{
	UI u,v,a;
	I bool operator<(RG EDGE x)const{return a<x.a;}
}e[M];//對邊排序
priority_queue<NODE>q;
UI n,L,p,he[N],ne[M],to[M],l[M],a[M],b[M],d[N],rt[M],lc[S],rc[S],f[S],mn[S],dep[S];
bool vis[N];
I UI in(){
	RG char G;
	while(c<'-')G;
	R x=c&15;G;
	while(c>'-')x*=10,x+=c&15,G;
	return x;
}
void build(R&u,R l,R r){//建初始并查集
	u=++p;
	if(l==r){mn[u]=d[f[u]=l];return;}
	R m=(l+r)>>1;
	build(lc[u],l,m);
	build(rc[u],m+1,r);
}
UI ins(R*u,R v,R t){//插入
	R l=1,r=n,m;
	while(l!=r){
		*u=++p;m=(l+r)>>1;
		if(t<=m)r=m,rc[*u]=rc[v],u=lc+*u,v=lc[v];
		else  l=m+1,lc[*u]=lc[v],u=rc+*u,v=rc[v];
	}
	return *u=++p;
}
UI getf(R rt,R t){//跳祖先
	R u,l,r,m;
	while(1){
		u=rt;l=1;r=n;
		while(l!=r){
			m=(l+r)>>1;
			if(t<=m)r=m,u=lc[u];
			else  l=m+1,u=rc[u];
		}
		if(t==f[u])break;
		t=f[u];
	}
	return u;
}
int main(){
	freopen("return.in","r",stdin);
	freopen("return.out","w",stdout);
	R T=in(),m,i,j,u,v,w;
	while(T--){
		p=0;n=in();m=in();//時刻注意清空變量！
		for(i=1;i<=m;++i){
			u=in();v=in();
			ne[++p]=he[u];to[he[u]=p]=v;
			ne[++p]=he[v];to[he[v]=p]=u;
			l[p]=l[p-1]=in();
			e[i]=(EDGE){u,v,a[p]=a[p-1]=in()};
		}
		memset(d,-1,(n+1)<<2);//dijkstra開始
		p=d[1]=0;q.push((NODE){1,0});
		while(!q.empty()){
			RG NODE cur=q.top();q.pop();
			if(vis[u=cur.u])continue;
			vis[u]=1;
			for(i=he[u];i;i=ne[i])
				if(d[to[i]]>d[u]+l[i])
					q.push((NODE){to[i],d[to[i]]=d[u]+l[i]});
		}
		R q=in(),k=in(),s=in(),lans=0;
		sort(e+1,e+m+1);
		for(i=1;i<=m;++i)b[i]=e[i].a;
		b[m+1]=s+1;L=unique(b+1,b+m+2)-b-1;//離散化，注意加入s+1
		build(rt[L],1,n);
		for(i=L-1,j=m;i;--i){
			rt[i]=rt[i+1];
			for(;j&&e[j].a==b[i];--j){
				if((u=getf(rt[i],e[j].u))==(v=getf(rt[i],e[j].v)))continue;//可優化的地方
				if(dep[u]>dep[v])swap(u,v);//按秩合并
				f[ins(&rt[i],rt[i],f[u])]=f[v];
				w=ins(&rt[i],rt[i],f[v]);
				f[w]=f[v];mn[w]=min(mn[u],mn[v]);//因為按秩合并是以min必須要記
				dep[w]=dep[v]+(dep[u]==dep[v]);//50分就是因為這一行！
			}
		}
		while(q--){
			v=(in()+k*lans-1)%n+1;u=(in()+k*lans)%(s+1);
			printf("%u\n",lans=mn[getf(rt[upper_bound(b+1,b+L+1,u)-b],v)]);
		}//謹慎選擇lower_bound和upper_bound
		memset(vis,0,n+1);
		memset(he,0,(n+1)<<2);
		memset(rt,0,(L+1)<<2);
		memset(lc,0,(p+1)<<2);
		memset(rc,0,(p+1)<<2);
		memset(f,0,(p+1)<<2);
		memset(mn,0,(p+1)<<2);
		memset(dep,0,(p+1)<<2);//該清空的都要清空
	}
	return 0;
}