牛半仙的妹子图

分析：

1. 考场看题首先判断是道图论，然后发现因为困难程度接受度是单增的，所以当前能走的边以后一定能走，所以便考虑走到每个类型的妹子家的最小困难度。
2. 因为每段路径的限制是这条路径上最大的困难度，所以是典型的最小生成树问题。找出最小生成树后树上遍历一遍即可求出分别能去每个点的最小接受程度。每个类型的最小所需接受程度对这个类型的每个点取min即可，记为g(i)。
3. 考虑到每个类型的妹子没有区别，所以我们不妨将g(i）排序，设得到的序列为f(i),易发现f(i)便是要收获i点愉悦值的最小所需接受程度。考虑如何求答案，虽然l与r的范围很大，但妹子类型<=600，即收获的愉悦值<=600，所以可以枚举收获的愉悦值，每种愉悦值的贡献就是(f(i+1)-f(i））*i，(不考虑边界)，对于1e5的询问来说已经可以过了。

一定要开long long，我考场就因没开导致直接70。

Code：

#include<bits/stdc++.h>
#define M 4000005
using namespace std;
long long mod;
struct edge{
    int t,next,w,f;
}t[M<<1],e[M<<1];
int head[M],ei,eii,n,m,f[M],Q,S,opt,g[M],c[M];
long long ans,las;   //开long long
inline void add(int x,int y,int w)
{
    t[++ei].t=y;
    t[ei].f=x;
    t[ei].next=head[x];
    head[x]=ei;
    t[ei].w=w;
}                                  //存边
int cmp(edge a,edge b)
{
    return a.w<b.w;
}
int fa[M];
inline int find(int x)
{
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
inline void kruskal()
{
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int u=find(e[i].f),v=find(e[i].t);
        if(u!=v)
        {
            add(e[i].f,e[i].t,e[i].w);
            add(e[i].t,e[i].f,e[i].w);
            fa[u]=v;
        }
    }
}   //克鲁斯卡尔建树
inline void dfs(int x,int fath,int minn)
{
    g[c[x]]=min(g[c[x]],minn);
    for(int i=head[x];i;i=t[i].next)
    {
        int v=t[i].t;
        if(v!=fath)dfs(v,x,max(minn,t[i].w));
    }
}   //求出到每种类型妹子家所需的最小接受程度
signed main()
{
//    freopen("sample.in","r",stdin);
    scanf("%d%d%d%d%d",&n,&m,&Q,&S,&opt);
    if(opt==1)scanf("%lld",&mod);
    int i,x,y,w,j,maxn=0;long long l,r;     // l与r也要开long long
    for(i=1;i<=n;i++)scanf("%d",&c[i]),maxn=max(maxn,c[i]);
    for(i=1;i<=maxn;i++)g[i]=2e9;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        e[++eii].f=x;e[eii].t=y;e[eii].w=w;
    }
    sort(e+1,e+1+eii,cmp);
    kruskal();
    dfs(S,0,0);
    for(i=1;i<=maxn;i++)f[i]=g[i];
    sort(f+1,f+1+maxn);f[++maxn]=2e9;     //排序，为了方便处理边界我加了一个极大值
    for(i=1;i<=Q;i++)
    {
        scanf("%lld%lld",&l,&r);
        if(opt==1)l=(l^las)%mod+1,r=(r^las)%mod+1;
        if(l>r)swap(l,r);ans=0;int pos=l;
        for(j=1;j<=maxn;j++)
        {
            if(f[j]>r)
            {
                ans+=(r-pos+1)*(j-1);
                break;
            }
            if(f[j]<=pos)continue;
            ans+=(long long)(f[j]-pos)*(j-1);
            pos=f[j];
        }                           // 统计答案，对于不同的愉悦值分别统计
        if(opt==1)las=ans;
        printf("%lld\n",ans);
    }
    return 0;
}