题目描述

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个n 个节点、m 条边的无向连通图（节点的编号从 1至 n）。我们依次用 l,a描述一条边的长度、海拔。 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免 的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的OIer，刚参加完ION2018 的他将踏上归程，回到他 温暖的家。 Yazid 的家恰好在魔力之都的 1 号节点。对于接下来 Q天，每一天Yazid 都会告诉你他的出发点 v，以及当天的水位线 p 。 每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。 Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是，第二天车会被重置，这意味着：

• 车会在新的出发点被准备好。
• Yazid 不能利用之前在某处停放的车。 Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。 本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。

• 输入输出格式

输入格式：

单个测试点中包含多组数据。输入的第一行为一个非负整数 T ，表示数据的组数。

接下来依次描述每组数据，对于每组数据：

第一行 2 个非负整数 n,m分别表示节点数、边数。

接下来 m 行，每行 4 个正整数 u,v,l,a描述一条连接节点 u,v 的、长度为 l、海拔为 a 的边。 在这里，我们保证 1≤u,v≤n 。

接下来一行 3 个非负数 Q,K,S其中 Q 表示总天数， K∈0,1 是一个会在下面被用到的系数， S 表示的是可能的最高水位线。

接下来 Q 行依次描述每天的状况。每行 2 个整数 v0;p0 描述一天：

这一天的出发节点为 v=(v0+K×lastans−1)modn+1。

这一天的水位线为 p=(p0+K×lastans)mod(S+1)。

其中 lastans 表示上一天的答案（最小步行总路程）。特别地，我们规定第 1 天时 lastans = 0。 在这里，我们保证 1≤v0≤n,0≤p0≤S1 。

对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。

输出格式：

依次输出各组数据的答案。对于每组数据：

• 输出 Q行每行一个整数，依次表示每天的最小步行总路程。

• 输入输出样例

输入样例#1：

1

4 3

1 2 50 1

2 3 100 2

3 4 50 1

5 0 2

3 0

2 1

4 1

3 1

3 2

输出样例#1：

0

50

200

50

150

输入样例#2：

1

5 5

1 2 1 2

2 3 1 2

4 3 1 2

5 3 1 2

1 5 2 1

4 1 3

5 1

5 2

2 0

4 0

输出样例#2：

0

2

3

1

说明

【样例1 解释】 第一天没有降水，Yazid 可以坐车直接回到家中。

第二天、第三天、第四天的积水情况相同，均为连接1; 2 号节点的边、连接3; 4 号 点的边有积水。

对于第二天，Yazid 从2 号点出发坐车只能去往3 号节点，对回家没有帮助。因此 Yazid 只能纯靠徒步回家。

对于第三天，从4 号节点出发的唯一一条边是有积水的，车也就变得无用了。Yazid只能纯靠徒步回家。

对于第四天，Yazid 可以坐车先到达2 号节点，再步行回家。

第五天所有的边都积水了，因此Yazid 只能纯靠徒步回家。

本组数据强制在线。

本组数据强制在线。

第一天的答案是 0 ，因此第二天的 v=(5+0−1)mod5+1=5， p=(2+0)mod(3+1)=2 。

第二天的答案是 2，因此第三天的 v=(2+2−1)mod5+1=4， p=(0+2)mod(3+1)=2 。

第三天的答案是 3 ，因此第四天的 v=(4+3−1)mod5+1=2 ， p=(0+3)mod(3+1)=3 。

所有测试点均保证 T≤3，所有测试点中的所有数据均满足如下限制：

• 任意两点之间都直接或间接通过边相连。

为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：

• 图形态：对于表格中该项为“一棵树”或“一条链”的测试点，保证m = n-1。 除此之外，这两类测试点分别满足如下限制：
• 一棵树：保证输入的图是一棵树，即保证边不会构成回路。
• 一条链：保证所有边满足u + 1 = v。
• 海拔：对于表格中该项为“一种”的测试点，保证对于所有边有a = 1。
• 强制在线：对于表格中该项为“是”的测试点，保证K = 1；如果该项为“否”， 则有K = 0。
• 对于所有测试点，如果上述对应项为“不保证”，则对该项内容不作任何保证。

• soulution

  正解好像是什么克鲁斯卡尔重构树吧，身为蒟蒻的我表示不会，从网上看到了可持久化并查集，仔细想了一下好像是可以做。
  那么如何运用可持久化并查集来过这道题呢？
  首先，题目要求最小步行路程到一点，而每次出发点和水位线不同，水位大于等于边的海拔都要被淹掉，也就是不能开车，由此可以想到并查集，判断每个点和哪些点是否联通，在判断这个联通块里的点哪个点距离１点最近，最短路可以预处理出来，听说SPFA炸了，在这里我用dijkstra。
  但每次水位线都不一样，而且强制在线，我们可以想到用可持久化并查集。每次询问一个水位线，运用二分找到当前并查集，直接查询就可以了。复杂度\(nlog^2n\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;typedef pair
         
           pr;priority_queue
          
           
            ,greater
            
              >kk;//dijstra堆优化struct TREE{ ll ln,rn;}t[15001000];struct node{ ll to,next,w,h;}a[800100];struct bian{ ll x,y,z,w; bool operator< (const bian &c) const { return w>c.w; }}p[1001000];ll last[500100],len,d[500001],vis[501000],tot,root[501000],fa[10100000],dep[10001000];//dep[]表示当前并查集深度，为了按秩合并，mn存下当前并查集哪个点到１点最近。ll hash[501000],mn[10001000];ll n,m,q,k,s;ll read(){ ll x=0,flag=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') flag=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*flag;}void add(ll a1,ll a2,ll a3,ll a4){ a[++len].to=a2; a[len].w=a3; a[len].h=a4; a[len].next=last[a1]; last[a1]=len;}ll lastans=0;void build(ll &node,ll l,ll r){ node=++tot; ll mid=(l+r)/2; if(l==r) {fa[node]=l;mn[node]=d[l];dep[node]=1;return;} build(t[node].ln,l,mid); build(t[node].rn,mid+1,r);}ll getpos(ll node,ll l,ll r,ll x){ if(l==r) return node; ll mid=(l+r)/2; if(x<=mid) return getpos(t[node].ln,l,mid,x); else return getpos(t[node].rn,mid+1,r,x);}ll getfa(ll node,ll x){ ll p=getpos(node,1,n,x); if(fa[p]==x) return p; else return getfa(node,fa[p]);}void gai(ll &node,ll last,ll l,ll r,ll x,ll y){ node=++tot; if(l==r) {fa[node]=y;dep[node]=dep[last];mn[node]=mn[last];return;} t[node]=t[last]; ll mid=(l+r)/2; if(x<=mid) gai(t[node].ln,t[last].ln,l,mid,x,y); else gai(t[node].rn,t[last].rn,mid+1,r,x,y);}void xiu(ll node,ll l,ll r,ll x){ if(l==r) {dep[node]++;return;} ll mid=(l+r)/2; if(x<=mid) xiu(t[node].ln,l,mid,x); else xiu(t[node].rn,mid+1,r,x);}ll minn(ll x,ll y){ if(x>y) return y; return x;}void gai1(ll &node,ll last,ll l,ll r,ll x){ node=++tot; if(l==r) {mn[node]=mn[last];fa[node]=fa[last];dep[node]=dep[last];return;} t[node]=t[last]; ll mid=(l+r)/2; if(x<=mid) gai1(t[node].ln,t[last].ln,l,mid,x); else gai1(t[node].rn,t[last].rn,mid+1,r,x);}void merge(ll x,ll y,ll i)//合并并查集{ if(dep[x]>dep[y]) swap(x,y); gai(root[i],root[i-1],1,n,fa[x],fa[y]); //很重要的两步，第一次修fa[x],第二次修改y的mn. gai1(root[i],root[i],1,n,fa[y]); ll orz=getpos(root[i],1,n,fa[y]); ll sto=getpos(root[i],1,n,fa[x]); mn[orz]=minn(mn[orz],mn[sto]); if(dep[x]==dep[y]) xiu(root[i],1,n,fa[y]);}void spfa()//dijkstra{ for(ll i=1;i<=n;i++) d[i]=1000000000000; d[1]=0; kk.push((pr){0,1}); while(!kk.empty()) { ll k=kk.top().second; kk.pop(); if(vis[k]) continue; vis[k]=1; for(ll i=last[k];i;i=a[i].next) { ll to=a[i].to; if(d[to]>d[k]+a[i].w) { d[to]=d[k]+a[i].w; kk.push((pr){d[to],to}); } } }}int main(){ ll t; cin>>t; while(t--) { memset(vis,0,sizeof(vis)); memset(root,0,sizeof(root));tot=0; lastans=0; len=0;memset(last,0,sizeof(last)); n=read();m=read(); for(ll i=1;i<=m;i++) { p[i].x=read();p[i].y=read();p[i].z=read();p[i].w=read(); add(p[i].x,p[i].y,p[i].z,p[i].w);add(p[i].y,p[i].x,p[i].z,p[i].w); } sort(p+1,p+1+m); for(int i=1;i<=m;i++) hash[i]=p[m-i+1].w; q=read();k=read();s=read(); spfa();//之前spfa炸了，没改函数名 build(root[0],1,n); for(ll i=1;i<=m;i++) { root[i]=root[i-1]; ll x=p[i].x,y=p[i].y; x=getfa(root[i],x);y=getfa(root[i],y); if(fa[x]!=fa[y]) merge(x,y,i); } for(ll i=1;i<=q;i++) { ll x,y; scanf("%lld%lld",&x,&y); x=(x+k*lastans-1)%n+1; y=(y+k*lastans)%(s+1); int tt=m-(upper_bound(hash+1,hash+1+m,y)-hash)+1; int orz=getfa(root[tt],x); printf("%lld\n",lastans=mn[orz]); } } return 0;}
            
           
          
         
        
       
      
     
    

复杂度有点高，洛谷上最后一个点跑3.7秒。