[CSP校内集训]替换游戏（tarjan+离散化）

题意

给一个范围\([0,n]\)，有两种变换方式，\(+k\)或者给定的\(m\)个\(x->y\)，但必须保证变换前后的数始终在范围内，给一个数\(x\)，求出它一直变换下去（注意不能得到了一个数之后返回上一步）可以得到的所有数的和的最大值\((n\leq 10^8 , m\leq 10^5 , k\leq n)\)，多组询问

思路

对两种方式建边，显然一个强连通分量中的点是都可以选到的，所以相当于多次询问求出DAG中从某个点出发的最长链，建反边拓扑即可

但是这道题的点数是\(10^8\)级别的，考虑到大多数连边都是第一种很规则的连边，所以有很多点是没有必要的，考虑离散化

将所有数按照对\(k\)取模的值分为\(k\)组，按照第一种方式连边后形成\(k\)条互不相交的链

将所有的第二种建边和询问用到的点离线下来离散化，即这些点需要单独考虑，这些点将链分为了很多小段，把每一个小段变成一个点

这时就可以发现点数已经与\(n\)无关了（有\(O(m+q)\)级别的点数），连接这些点后就可以像上面的暴力一样做了

#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\n",f[color[q[i]]]);
    return 0;
}