题目信息
丢传送门
题解
65%
很容易想到离线做法：
将边按权值从高到低排序，丢进并查集处理。同时将询问离线，按水位线从高到低。
并查集维护当前水位下没有积水的连通块，以及块中离1号点最近的距离。当然，还得跑个单源最短路来求距离。由于水位线是在递减，并查集不会有删除操作,说明这样做是正确的。
然而这题强制在线……
100%
我们发现并查集处理不了这道题
但是
可持久化并查集可以……
可持久化并查集可以用【可持久化数组+并查集】理解，可持久化数组可以用【可持久化线段树】理解，可持久化线段树也就是非权值线段树版【主席树】。于是正解的思路就出来了。
同65%的加边操作，只是每条边加完以后记录版本。查询时访问对应的版本，求出点所在连通块到1号点的最小距离。
不过这题恶心的地方在代码和一些细节。调了2个小时，如果真在考场上肯定写完65%走人。
注意：
- 海拔需要离散
- 并查集不能路径压缩，不然空间会爆。需要按秩合并。按秩合并相当于启发式合并，深度小的合并到深度大的上。这里又会引出一个细节——当两个根深度相同，需要人为给合并后的那个深度加一以保证正确性。
我这里更新后的块内最小距离是记录到根编号上，比较神秘。据说开个真的并查集，用可持久化数组记录变化要快很多，有兴趣的可以尝试一下。
3.47K AC：
#include <bits/stdc++.h>
#define mp make_pair
#define mem(O) memset(O,0,sizeof(O))
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
inline char nc(){
#ifdef nijisanji
return getchar();
#endif
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int red(){
int x=0,f=1;char ch=nc();for(;!isdigit(ch);ch=nc())if(ch=='-')f=-1;
for(;isdigit(ch);ch=nc())x=x*10+ch-'0';return x*f;
}
const int N = 5e5+10;
int n,m,p;
int lis[N];
struct edge{int u,v,w,h,nxt;}e[N<<1],E[N];
int head[N],add_cnt;
inline void add(int u,int v,int w){e[++add_cnt]=(edge){u,v,w,0,head[u]};head[u]=add_cnt;}
bool cmp(edge a,edge b){return a.h>b.h;}
int rt[N],fa[N<<5],dep[N<<5];ll mn[N<<5];
namespace SHR{
ll dis[N];int vis[N];
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
priority_queue <P,vector<P>,greater<P> > q;
dis[1]=0,q.push(mp(dis[1],1));
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;vis[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w){
dis[v]=dis[u]+e[i].w;
q.push(mp(dis[v],v));
}
}
}
}
}
namespace HJT{
int sz,ls[N<<5],rs[N<<5];
#define mid (tl+tr>>1)
void build(int &o,int tl,int tr){
o=++sz;
if(tl==tr) return fa[o]=tl,mn[o]=SHR::dis[tl],dep[o]=0,void();
build(ls[o],tl,mid),build(rs[o],mid+1,tr);
}
void herige(int &o,int per,int tar,int tl,int tr){
o=++sz;
ls[o]=ls[per],rs[o]=rs[per];
if(tl==tr){fa[o]=fa[per],dep[o]=dep[per],mn[o]=mn[per];return;}
if(tar<=mid) herige(ls[o],ls[per],tar,tl,mid);
else herige(rs[o],rs[per],tar,mid+1,tr);
}
void merge(int &o,int per,int tar,int tl,int tr,int f){
o=++sz;
ls[o]=ls[per],rs[o]=rs[per];
if(tl==tr){fa[o]=f,dep[o]=dep[per],mn[o]=mn[per];return;}
if(tar<=mid) merge(ls[o],ls[per],tar,tl,mid,f);
else merge(rs[o],rs[per],tar,mid+1,tr,f);
}
void update(int o,int tar,int tl,int tr){
if(tl==tr) return ++dep[o],void();
if(tar<=mid) update(ls[o],tar,tl,mid);
else update(rs[o],tar,mid+1,tr);
}
int query(int o,int tar,int tl,int tr){
if(tl==tr) return o;
if(tar<=mid) return query(ls[o],tar,tl,mid);
else return query(rs[o],tar,mid+1,tr);
}
#undef mid
}
namespace UDF{
int find(int o,int tar){
int u=HJT::query(o,tar,1,n);
if(fa[u]==tar) return u;
return find(o,fa[u]);
}
void merge(int x,int y,int i){
int fx=find(rt[i],x),fy=find(rt[i],y);
if(fa[fx]!=fa[fy]){
if(dep[fx]>dep[fy]) swap(fx,fy);
HJT::merge(rt[i],rt[i-1],fa[fx],1,n,fa[fy]);
HJT::herige(rt[i],rt[i],fa[fy],1,n);
int py=HJT::query(rt[i],fa[fy],1,n);
int px=HJT::query(rt[i],fa[fx],1,n);
mn[py]=min(mn[py],mn[px]);
if(dep[fx]==dep[fy]) HJT::update(rt[i],fa[fy],1,n);
}
}
}
void discrete(){
sort(E+1,E+m+1,cmp);
for(int i=1;i<=m;++i) lis[i]=E[m-i+1].h;
}
ll lastans=0;
void solve(){
n=red(),m=red();
for(int i=1;i<=m;++i){
int u=red(),v=red(),l=red(),a=red();
add(u,v,l),add(v,u,l);
E[i]=(edge){u,v,l,a,0};
}
SHR::dijkstra();
discrete();
HJT::build(rt[0],1,n);
for(int i=1;i<=m;++i){
rt[i]=rt[i-1];
UDF::merge(E[i].u,E[i].v,i);
}
ll Q=red(),K=red(),S=red();
for(int i=1;i<=Q;++i){
ll u=(red()+K*lastans-1)%n+1;
ll pl=(red()+K*lastans)%(S+1);
int ver=m-(upper_bound(lis+1,lis+m+1,pl)-lis)+1;
lastans=mn[UDF::find(rt[ver],u)];
printf("%lld\n",lastans);
}
}
void clear(){
mem(SHR::vis),mem(rt),mem(head);
add_cnt=0,HJT::sz=0,lastans=0;
}
int main(){
int T=red();
while(T--){
solve();
if(T) clear();
}
return 0;
}
