P4768 [NOI2018] 归程

“当梦想指路至无知的远方，醒来时分的少年，是否应该考虑随着漫雨，踏上归途。”

~~损失一个亿的调题技巧~~。（指错失了 $\text{l18q AK IOI}$ 的机会，$\textcolor{gold}{\text{Au}}$ 爷久久不能释怀）

首先，$n,m,q$ 都是 $\mathcal O(n\log n)$ 级别的，说明不能限制在 $q$ 上，得考虑一大堆预处理。然后把图建出来之后会发现，因为车子只能使用一次，那么我们能够零体力到达的点一定是一个包含了起点，且海拔皆在水位线之上的一个连通块，而对于其他部分，最短路径不变，可以预处理：用 $\text{Dijkstra}$ 预处理可以达到 $\mathcal O(n\log m)$ ，注意：这里并不能使用 $\text{Spfa}$ ，会被卡掉。（出题人出言“$\text{Spfa}$ 已经死了”）

我们所求的答案就是该连通块 $\text{S}$ 里的 $\displaystyle\min_{s\in S}Dist[s]$ 。那有没有方法可以快速找到所在连通块，且与询问无关呢？考虑一种贪心思路，即按照海拔高度依次处理使得对于 $Dp[x]$ 则是之前所有里的答案。

然后我们还要保证连通，则肯定不考虑 $\mathcal O(1)$ 查询，考虑 $\mathcal O(\log)$ 。如果是数据结构的话，可以考虑堆，满足顺序的性质，但是并不太好搞连通性，于是考虑从堆开始扩展，联想到 $\text{Kruskal}$ 重构树，然后理所当然出来一个性质，海拔从子结点到父结点依次变小，然后用 $Dp[x]$ 表示以 $x$ 为根的子树内的最小答案，一个简单的树型 $\text{dp}$ 直接 $\mathcal O(n)$ 搞掉。

然后考虑如何从询问扩展到已处理部分——能够到达的连通块肯定满足 $l_i>s$ ，而重构树内海拔由小到大，我们就需要找到一个深度最小的点，满足 $l_e>s$ ，然后 $dp[e]$ 就是我们所求的答案。

调了老半天的原因有几个，拿来避雷：

在进行 $\text{Dijkstra}$ 预处理的时候，点数为 $n$ ，而在重构树之后，点数会变成 $2n-1$ ，所以 for 循环应该套的是 Idx 而不是 N 。
空间十分玄学（也不是很玄学），同样因为是重构树，导致很多东西都需要开到两倍。
多组数据，记得清空；以及如果最短路和重构树共用一个链式前向星的话，也要记得清空。

因为打的时候比较紊乱，所以写的也就比较紊乱，所需要的变量都是定义在函数之前的，比较分散，也就导致 Dist[MAXN] 没有二倍。

AC Code

// Problem: P4768 [NOI2018] 归程
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4768
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// Written by: Eternity

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=getchar(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
template<>
inline void write(char c)
{
    putchar(c);
}
template<>
inline void write(char *s)
{
    while(*s!='\0') putchar(*s++);
}
template<>
inline void write(const char *s)
{
    while(*s!='\0') putchar(*s++);
}
template<class T,class ...T1>
inline void write(T x,T1 ...x1)
{
    write(x),write(x1...);
}
template<class T>
inline void checkMax(T &x,T y)
{
    x=x>y?x:y;
}
template<class T>
inline void checkMin(T &x,T y)
{
    x=x<y?x:y;
}
const int MAXN=2e5+10,MAXM=4e5+10;
int Test,N,M,Q,K,S,Val[MAXN<<1];
struct G
{
	int next,to,val;
}Edge[MAXM<<1];
struct Edges
{
	int u,v,h;
}Ed[MAXM];
int Head[MAXN<<1],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
inline void init()
{
	memset(Head,0,sizeof(Head)),Total=0;
	read(N,M);
	for(int i=1,u,v,l,h;i<=M;++i)
	{
		read(u,v,l,h);addEdge(u,v,l);
		Ed[i]=(Edges){u,v,h};
	}
	read(Q,K,S);
}
struct Que
{
	int x,d;
	Que(int x=0,int d=0):x(x),d(d){}
	bool operator<(const Que &x) const
	{
		return x.d<d;
	}
};
int Dist[MAXN];
bool Vis[MAXN];
inline void Dijkstra(int st)
{
	std::priority_queue<Que>Q;
	Q.push(Que(st,0));
	memset(Dist,0x3f,sizeof(Dist)),Dist[st]=0;
	memset(Vis,0,sizeof(Vis));
	while(!Q.empty())
	{
		int u=Q.top().x;Q.pop();
		if(Vis[u]) continue;
		Vis[u]=1;
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(Dist[v]>Dist[u]+Edge[e].val)
			{
				Dist[v]=Dist[u]+Edge[e].val;
				if(!Vis[v]) Q.push(Que(v,Dist[v]));
			}
		}
	}
}
int Idx;
struct Dsu
{
    int Rt[MAXN<<1];
    inline void init(int n)
    {
        for(int i=1;i<=2*n;++i) Rt[i]=i;
    }
    inline int getRt(int x)
    {
        return Rt[x]==x?x:Rt[x]=getRt(Rt[x]);
    }
    inline int merge(int x,int y)
    {
        int p=getRt(x),q=getRt(y);
        Rt[p]=Rt[q]=++Idx;
        return Idx;
    }
    inline bool connect(int x,int y)
    {
        int p=getRt(x),q=getRt(y);
        return p==q;
    }
}Dsu;
inline bool cmp(Edges a,Edges b)
{
	return a.h>b.h;
}
inline void Kruskal()
{
	memset(Head,0,sizeof(Head)),Total=0;
	Idx=N;
	std::sort(Ed+1,Ed+M+1,cmp);
	Dsu.init(N);
	for(int i=1;i<=M;++i)
	{
		auto e=Ed[i];
		int p1=Dsu.getRt(e.u),p2=Dsu.getRt(e.v);
		if(p1==p2) continue;
		int lca=Dsu.merge(p1,p2);Val[lca]=e.h;
		addEdge(lca,p1,0),addEdge(lca,p2,0);
	}
}
int Dp[MAXN<<1],Mul[MAXN<<1][25];
void dfsTree(int x,int last)
{
	Dp[x]=Dist[x];
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Mul[v][0]=x;
		checkMin(Dp[x],Dp[v]);
	}
}
inline void Multi()
{
	for(int i=1;i<25;++i)
		for(int x=1;x<=Idx;++x)
			Mul[x][i]=Mul[Mul[x][i-1]][i-1];
}
inline int getLc(int x,int val)
{
	for(int i=24;i>=0;--i) if(Val[Mul[x][i]]>val) x=Mul[x][i];
	return x;
}
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(Test);
    while(Test--)
    {
    	init();
    	Dijkstra(1),Kruskal();
    	dfsTree(Idx,0),Multi();
    	int lastans=0;
		for(int st,s;Q--;)
    	{
    		read(st,s);
			st=(st+K*lastans-1)%N+1,s=(s+K*lastans)%(S+1);
			write(lastans=Dp[getLc(st,s)],'\n');
    	}	
    }
    return 0;
}
/*

*/