牛半仙的妹子图

不难发现，能否走到这个点仅与起点到这个点路径最小的最大值有关，因此显然可以先生成一棵生成树，然后统计答案。
然后对于每次询问，如果 $l$ 比大于等于能走到的最小值，那么直接说明 $[l,r]$ 都可以走，否则答案即为 $0$
然而数据太大，考虑离散化，此时破坏了 $[l,r]$ 离散化成了一个区间，由于有在线数据，我们无法把 $[l,r]$ 也离散化，因此考虑类似分块的方法，用两个树状数组，处理前缀和和前缀和的前缀和
注意第一个树状数组的意义是小于等于 $x$ 这段区间能得到的愉悦值和，第二个树状数组的意义是 $[1,b(r+1)-1]$ 这个区间前缀和的愉悦值（ $b(x)$ 意为离散化之前的数，记得插入一个极大值）
然后就可以类似分块那样统计答案了，复杂度是 $O(n\log n)$

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define int long long
using namespace std;

namespace mstd{

    inline void qread(int &x)
    {
        x=0; int f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }

    inline void mqread(long long &x)
    {
        x=0; long long f=1;
        static char c=getchar();
        while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
        while(isdigit(c)) x=(x*10+c-'0'),c=getchar();
        x*=f;
    }

}

const int maxn=500500;

int n,m,head[maxn],size;
int q,st,opt,modp,f[maxn],lasans;
int b[maxn],tot,C;
int d[maxn],bl[maxn],cst[maxn];

struct ctree{

    int c[maxn];

    int lowbit(int x)
    {
        return x&(-x);
    }

    inline void add(int x,int target)
    {
        while(x<=C) c[x]+=target,x+=lowbit(x);
        return ;
    }

    inline int ask(int x)
    {
        int ans=0;
        while(x) ans+=c[x],x-=lowbit(x);
        return ans;
    }
}st1,st2,st3;

struct edge{
    int next,to,dis;
}e[maxn<<1];

struct medge{
    int x,y,dis;
    bool operator <(const medge &ano)
    const {
        return dis<ano.dis;
    }
}_e[maxn];

inline void addedge(int next,int to,int dis)
{
    e[++size].to=to;
    e[size].dis=dis;
    e[size].next=head[next];
    head[next]=size;
}

inline void getdis(int t,int fat)
{
    int i,j,k;
    for(i=head[t];i;i=e[i].next)
    {
        j=e[i].to;
        if(j==fat) continue;
        k=e[i].dis;
        d[j]=max(k,d[t]);
        getdis(j,t);
    }
}

int getfather(int x)
{
    if(x==f[x]) return x;
    return f[x]=getfather(f[x]);
}

inline void gettree()
{
    int i,j;
    int p=0;
    for(i=1;i<=n;i++) f[i]=i;
    sort(_e+1,_e+m+1);
    for(i=1;i<=m;i++)
    {
        int x=_e[i].x;
        int y=_e[i].y;
        int edis=_e[i].dis;
        int xx=getfather(x);
        int yy=getfather(y);
        if(xx==yy) continue;
        p++;
        f[xx]=yy;
        addedge(x,y,edis);
        addedge(y,x,edis);
        if(p==n-1) break;
    }
    return ;
}

int cmst=0;

int getans(int l,int r)
{
    cmst++;
    int ll=l,ans;
    if(b[1]<=l) ans=upper_bound(b+1,b+tot+1,r)-b;
    else ans=0;
    ll=upper_bound(b+1,b+tot+1,l)-b;
    int rigsize=r-b[ans-1]+1;
    int lefsize=b[ll]-l;
    if(ll==ans) return (st2.ask(ll-1)*(r-l+1));
    else if(ans-ll==1) return(st2.ask(ans-1)*(rigsize)+st2.ask(ll-1)*(lefsize));
    else return(st2.ask(ans-1)*(rigsize)+st2.ask(ll-1)*(lefsize)+st3.ask(ans-2)-st3.ask(ll-1));
    return 0;
}

inline void solve(int l,int r)
{
    if(opt) {l=(l^lasans)%modp+1,r=(r^lasans)%modp+1;}
    l++,r++;
    if(l>r) swap(l,r); 
    //printf("%d\n",lower_bound(b+1,b+tot+1,2)-b);
    printf("%lld\n",lasans=getans(l,r));
    return ;
}

inline void _prework()
{
    int i;
    for(i=1;i<=n;i++) st1.add(d[i],1);
    for(i=1;i<=600;i++) if(cst[i]!=0x3f3f3f3f) st2.add(cst[i],1);
    for(i=1;i<C;i++) st3.add(i,st2.ask(i)*(b[i+1]-b[i]));
    return ;
} 

signed main()
{
//    freopen("sample.in","r",stdin);
//    freopen("samplee.out","w",stdout);
    int i,j;
    mstd::qread(n); 
    mstd::qread(m);
    mstd::qread(q);
    mstd::qread(st);
    mstd::qread(opt);
    if(opt) mstd::qread(modp);
    int t1,t2,t3;
    for(i=1;i<=n;i++) mstd::qread(bl[i]); 
    for(i=1;i<=m;i++)
    {
        mstd::qread(t1);
        mstd::qread(t2);
        mstd::qread(t3);
        //cin>>t1>>t2>>t3; 
        t3++;
        _e[i].x=t1;
        _e[i].y=t2;
        _e[i].dis=t3;
    }
    gettree();
    d[st]=1;
    getdis(st,st);
    memset(cst,0x3f,sizeof(cst));
    for(i=1;i<=n;i++) b[i]=d[i];
    int sz=n;
//    for(i=1;i<=n;i++) 
//    {
//        if(b[i]!=1) b[++sz]=b[i]-1;
//        b[++sz]=b[i]+1;
//    }
    sort(b+1,b+sz+1);
    b[++sz]=(int)1e9+20;
    sort(b+1,b+sz+1);
    tot=unique(b+1,b+sz+1)-b-1;
    C=tot;
    for(i=1;i<=n;i++) d[i]=lower_bound(b+1,b+tot+1,d[i])-b;
    for(i=1;i<=n;i++) cst[bl[i]]=min(cst[bl[i]],d[i]);
    _prework();
    int l,r;
    for(i=1;i<=q;i++)
    {
        mstd::qread(l);
        mstd::qread(r);
        solve(l,r);
    }
    return 0;
}