题意
给一个范围([0,n])，有两种变换方式，(+k)或者给定的(m)个(x->y)，但必须保证变换前后的数始终在范围内，给一个数(x)，求出它一直变换下去（注意不能得到了一个数之后返回上一步）可以得到的所有数的和的最大值((nleq 10^8 , mleq 10^5 , kleq n))，多组询问
思路
对两种方式建边，显然一个强连通分量中的点是都可以选到的，所以相当于多次询问求出DAG中从某个点出发的最长链，建反边拓扑即可
但是这道题的点数是(10^8)级别的，考虑到大多数连边都是第一种很规则的连边，所以有很多点是没有必要的，考虑离散化
将所有数按照对(k)取模的值分为(k)组，按照第一种方式连边后形成(k)条互不相交的链
将所有的第二种建边和询问用到的点离线下来离散化，即这些点需要单独考虑，这些点将链分为了很多小段，把每一个小段变成一个点
这时就可以发现点数已经与(n)无关了（有(O(m+q))级别的点数），连接这些点后就可以像上面的暴力一样做了
P.S. 点权请自行用等差数列解决
#include<bits/stdc++.h>
#define N 600005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int n,m,k,ndsum;
int dfn[N],low[N],cp,col,color[N];//tarjan
int st[N],top,rd[N];//拓扑
int b[N],c[N],len;//离散化特例
ll sum[N],val[N],f[N];
vector<int> son[N];//新图
struct E { int u,v; } e[N];
int q[N];//离线询问 和 边
struct Edge
{
int next,to;
}edge[N<<2];int head[N],cnt;
void add_edge(int from,int to)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
head[from]=cnt;
}
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
void tarjan(int rt)
{
dfn[rt]=low[rt]=++cp;
st[++top]=rt;
for(int i=head[rt];i;i=edge[i].next)
{
int v=edge[i].to;
if(!dfn[v])
{
tarjan(v);
low[rt]=Min(low[rt],low[v]);
}
else if(!color[v]) low[rt]=Min(low[rt],dfn[v]);
}
if(dfn[rt]==low[rt])
{
color[rt]=++col;
sum[col]+=val[rt];
while(st[top]!=rt)
{
sum[col]+=val[st[top]];
color[st[top--]]=col;
}
--top;
}
}
void init()
{
for(int i=1;i<=ndsum;++i)
{
for(int j=head[i];j;j=edge[j].next)
{
int v=edge[j].to;
if(color[i]!=color[v])
{
son[color[v]].push_back(color[i]);
++rd[color[i]];
}
}
}
queue<int> q;
for(int i=1;i<=col;++i) if(!rd[i]) q.push(i),f[i]=sum[i];
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=0,t=son[u].size();i<t;++i)
{
int v=son[u][i];
f[v]=Max(f[v],f[u]+sum[v]);
if(--rd[v]==0) q.push(v);
}
}
}
bool cmp(int x,int y)
{
return (b[x]%k==b[y]%k ? b[x]<b[y] : b[x]%k<b[y]%k);//按颜色排序
}
int get_max(int n,int x)//找到满足 <= n 的 最大的 mod k==x的数
{
int ret=n/k*k+x;
return ret-(ret>n)*k;
}
ll get_sum(int x,int y)//求(x,y]的和
{
return (ll)(y-x)*(x+y+k)/(2*k);
}
void work()
{
for(int i=1;i<=len;++i) c[i]=i;
sort(c+1,c+len+1,cmp);//连基础边
for(int i=1;i<=len;++i)
{
val[c[i]]=b[c[i]];
int co=b[c[i]]%k;
if(i==len||b[c[i]]%k!=b[c[i+1]]%k)//一个颜色的最后一个点
{
int maxx=get_max(n,co);
if(maxx!=b[c[i]])
{
++ndsum;
add_edge(c[i],ndsum);
val[ndsum]=get_sum(b[c[i]],maxx);
}
}
else
{
int maxx=get_max(b[c[i+1]]-1,co);
if(maxx>b[c[i]])
{
++ndsum;
add_edge(c[i],ndsum);
add_edge(ndsum,c[i+1]);
val[ndsum]=get_sum(b[c[i]],maxx);
}
else add_edge(c[i],c[i+1]);
}
}
for(int i=1;i<=m;++i) add_edge(e[i].u,e[i].v); //连特殊边
for(int i=1;i<=ndsum;++i) if(!dfn[i]) tarjan(i);
}
int main()
{
freopen("substitution.in","r",stdin);
freopen("substitution.out","w",stdout);
//读入
read(n);read(m);read(k);
for(int i=1;i<=m;++i)
{
read(e[i].u);read(e[i].v);
b[++len]=e[i].u;
b[++len]=e[i].v;
}
int T; read(T);
for(int i=1;i<=T;++i)
{
read(q[i]);
b[++len]=q[i];
}
//离散化
sort(b+1,b+len+1);
len=unique(b+1,b+len+1)-b-1;
ndsum=len;
for(int i=1;i<=m;++i)
{
e[i].u=lower_bound(b+1,b+len+1,e[i].u)-b;
e[i].v=lower_bound(b+1,b+len+1,e[i].v)-b;
}
for(int i=1;i<=T;++i) q[i]=lower_bound(b+1,b+len+1,q[i])-b;
work();
init();
for(int i=1;i<=T;++i) printf("%lld
",f[color[q[i]]]);
return 0;
}