题目传送门
题意分析
考虑一个在线的做法。记 \(w,h\) 表示边的长度和海拔。
单独考虑每一次询问，如果水位线 \(p<h\)，则这条边是可以走的。否则这条边等价于没有。
考虑并查集维护边的合并，查询就查询当前连通块内离 \(1\) 的最短路长度即可。
但是水位线会变化，因此 \(h\) 从大到小合并并查集，进行可持久化操作即可。
查询更简单，二分找到对应版本，查询并查集内的最短路最小值即可。
时间复杂度 \(\mathcal O\left(T(m+q)\log n\right)\)。
AC 代码
常数略大。
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
constexpr const int N=200000,M=400000,Q=400000;
struct edge{int u,v,w,h;
}e[M+1];
int n,m,q;
int dis[N+1];
vector<pair<int,int>>g[N+1];
void Dijkstra(){priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;static bool vis[N+1];memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));dis[1]=0;q.push({dis[1],1});while(q.size()){int x=q.top().second;q.pop();if(vis[x]){continue;}vis[x]=true;for(auto [v,w]:g[x]){if(vis[v]){continue;}if(dis[x]+w<dis[v]){dis[v]=dis[x]+w;q.push({dis[v],v});}}}
}
struct value{int f,size,d;
};
struct segTree{int root[M+1],size;typedef value (*fp)(int);struct node{int l,r;value x;int lChild,rChild;}t[N*80+1];segTree(){size=0;}void clear(){size=0;}int create(node x){t[++size]=x;return size;}int clone(int p){t[++size]=t[p];return size;}int build(int l,int r,fp func){node x={l,r};if(l==r){x.x=func(l);return create(x);}int mid=l+r>>1;x.lChild=build(l,mid,func);x.rChild=build(mid+1,r,func);return create(x);}int update(int p,int x,value k){p=clone(p);if(t[p].l==t[p].r){t[p].x=k;return p;}if(x<=t[t[p].lChild].r){t[p].lChild=update(t[p].lChild,x,k);}else{t[p].rChild=update(t[p].rChild,x,k);}return p;}void update(int v,int i,int x,value k){root[i]=update(root[v],x,k);}value query(int p,int x){if(t[p].l==t[p].r){return t[p].x;}if(x<=t[t[p].lChild].r){return query(t[p].lChild,x);}else{return query(t[p].rChild,x);}}value query(int v,int i,int x){root[i]=root[v];return query(root[i],x);}void copy(int v,int i){root[i]=root[v];}
};
struct dsu{segTree t;void build(int n){t.clear();t.root[0]=t.build(1,n,[](int x){return value{x,1,dis[x]};});}int find(int v,int i,int x){int fx=t.query(v,i,x).f;if(fx!=x){return find(v,i,fx);}else{return x;}} void cancel(int v,int i){t.copy(v,i);}void merge(int v,int i,int a,int b){cancel(v,i);a=find(i,i,a);b=find(i,i,b);if(a==b){return;}value A=t.query(i,i,a),B=t.query(i,i,b);if(A.size<B.size){t.update(i,i,a,{b,A.size,A.d});t.update(i,i,b,{B.f,A.size+B.size,min(A.d,B.d)});}else{t.update(i,i,b,{a,B.size,B.d});t.update(i,i,a,{A.f,A.size+B.size,min(A.d,B.d)});}}int query(int v,int x){x=find(v,v,x);return t.query(v,v,x).d;}
}dsu;
void pre(){for(int i=1;i<=n;i++){g[i].resize(0);}for(int i=1;i<=m;i++){auto [u,v,w,h]=e[i];g[u].push_back({v,w});g[v].push_back({u,w});}Dijkstra();dsu.build(n);sort(e+1,e+m+1,[](edge a,edge b){return a.h>b.h;});for(int i=1;i<=m;i++){dsu.merge(i-1,i,e[i].u,e[i].v); }
}
int query(int v,int p){int l=1,r=m,ans=-1;while(l<=r){int mid=l+r>>1;if(e[mid].h>p){ans=mid;l=mid+1;}else{r=mid-1;}}if(ans==-1){return dis[v];}return dsu.query(ans,v);
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int T;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=m;i++){auto &[u,v,w,h]=e[i];cin>>u>>v>>w>>h;}pre();int k,s,lastans=0;cin>>q>>k>>s;for(int i=1;i<=q;i++){int v,p;cin>>v>>p;v=(v+k*lastans-1)%n+1;p=(p+k*lastans)%(s+1);lastans=query(v,p);cout<<lastans<<'\n';}}cout.flush();/*fclose(stdin);fclose(stdout);*/return 0;
}