T2_牛客博客

求一个式子 $Ans=\sum_{w=l}^r f(w)$
其中 $f(w)$ 表示为不经过边权超过 $i$ 的边，从 $x$ 开始能够走到的不同颜色点的数量

可以使用前缀和作差，有 $Ans=\sum_{i=1}^r f(w) -\sum_{i=1}^{l-1}f(w)$
那么这个式子的意义就是，每次不经过边权超过 $1,2,3,...r$ 的边权能够到达的不同颜色数量，减去不经过边权超过 $1,2,3...l-1$ 能够到达的不同颜色数量.

显然， $f(i)$ 与 $f(i-1)$ 是有关系的，这个是可以自己手推的

但是对于此题 $w_i\le 1e9$ ，显然需要离散化，而离散化之后 $i$ 和 $i+1$ 之间的数，其值全为 $f(i)$ .

那么此题就可做了.

实现代码时用了一个前缀和数组 $g[i]=\sum_{i=0}^{w[i]-1}f(i)$ ，答案就可以 $\mathcal O(\log n)$ 计算，总复杂度 $\mathcal O(n\log n)$

话说我被卡常是没想到的......

#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;

namespace IO{
    #define rep(i,__l,__r) for(signed i=(__l),i##_end_=(__r);i<=i##_end_;++i)
    #define fep(i,__l,__r) for(signed i=(__l),i##_end_=(__r);i>=i##_end_;--i)
    #define erep(i,u) for(signed i=tail[u],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
    #define writc(a,b) fwrit(a),putchar(b)
    #define mp(a,b) make_pair(a,b)
    #define fi first
    #define se second
    typedef long long ll;
    // typedef pair<int,int> pii;
    typedef unsigned long long ull;
    typedef unsigned uint;
    #define Endl putchar('\n')
    // #define int long long
    // #define int unsigned
    // #define int unsigned long long

    #define cg (c=getchar())
    template<class T>inline void readin(T& x){
        char c;bool f=0;
        while(cg<'0'||'9'<c)f|=(c=='-');
        for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
        if(f)x=-x;
    }
    template<class T>inline T readin(T x){
        x=0;char c;bool f=0;
        while(cg<'0'||'9'<c)f|=(c=='-');
        for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));
        return f?-x:x;
    }
    #undef cg
    template<class T>void fwrit(const T x){
        if(x<0)return (void)(putchar('-'),fwrit(-x));
        if(x>9)fwrit(x/10);
        putchar(x%10^48);
    }
    template<class T>inline T Max(const T x,const T y){return x<y?y:x;}
    template<class T>inline T Min(const T x,const T y){return x<y?x:y;}
    template<class T>inline T fab(const T x){return x>0?x:-x;}
    template<class T>T gcd(const T a,const T b){return b?gcd(b,a%b):a;}
    inline void getInv(int inv[],const int lim,const int MOD){
        inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
    }
    inline ll mulMod(const ll a,const ll b,const ll mod){//long long multiplie_mod
        return ((a*b-(ll)((long double)a/mod*b+1e-8)*mod)%mod+mod)%mod;
    }
}
using namespace IO;

#define int long long

const int maxn=5e5;
const int maxm=5e5;
const int inf=1e9+5;

struct edge{int to,nxt,w;}e[maxm*2+5];
int tail[maxn+5],ecnt;
inline void add_edge(const int u,const int v,const int w){
    e[++ecnt]=edge{v,tail[u],w};tail[u]=ecnt;
    e[++ecnt]=edge{u,tail[v],w};tail[v]=ecnt;
}

int n,m,q,x,opt,M,las;
int c[maxn+5];

inline void Init(){
    n=readin(1ll),m=readin(1ll),q=readin(1ll),x=readin(1ll),opt=readin(1ll);
    if(opt==1)M=readin(1ll);
    rep(i,1,n)c[i]=readin(1ll);
}

int w_arr[maxm+5];

inline void Get_G(){
    int u,v;
    rep(i,1,m){
        u=readin(1ll),v=readin(1ll),w_arr[i]=readin(1ll);
        add_edge(u,v,w_arr[i]);
    }
}

/** @brief 将边权离散化*/
inline void Get_hash(){
    sort(w_arr+1,w_arr+m+1);
    m=unique(w_arr+1,w_arr+m+1)-w_arr-1;
    rep(i,1,ecnt)e[i].w=lower_bound(w_arr+1,w_arr+m+1,e[i].w)-w_arr;
}

struct node{int u,maxw;
    inline int operator <(const node rhs)const{
        return !(maxw<rhs.maxw);
    }
};
priority_queue<node>Q;
/** @brief 注意, 这里的 f 下标大小为 maxm*/
int f[maxm+5];
/** @brief g[i] = Σ 0~w[i]-1, val[i]*/
int g[maxm+5];
/** @brief 这种颜色被边权为多少时用过*/
int used_col[605];
/** @brief 这个点被 maxw 为多少时到访过*/
int dis[maxn+5];
inline void Dijkstra(){
    rep(i,1,n)dis[i]=inf;
    rep(i,0,600)used_col[i]=m+1;
    Q.push(node{x,0});
    dis[x]=0,used_col[c[x]]=0,++f[0];
    while(!Q.empty()){
        int u=Q.top().u,w=Q.top().maxw;Q.pop();
        if(w>dis[u])continue;
        // printf("Now u == %lld, w == %lld\n",u,w);
        for(int i=tail[u],v,tow;i;i=e[i].nxt){
            v=e[i].to,tow=Max(w,e[i].w);
            if(tow>=dis[v])continue;
            dis[v]=tow;
            // printf("When %lld is going to go to %lld, tow == %lld, used_col[c[%lld]] == %lld\n",u,v,tow,v,used_col[c[v]]);
            if(tow<used_col[c[v]]){
                --f[used_col[c[v]]];
                ++f[tow];
                // printf("++f[%lld]\n",tow);
                used_col[c[v]]=tow;
            }
            Q.push(node{v,tow});
        }
    }
    rep(i,1,m)f[i]+=f[i-1];
    g[0]=0;
    rep(i,1,m)g[i]=g[i-1]+1ll*(w_arr[i]-w_arr[i-1])*f[i-1];
}

inline void Get_query(){
    int l,r,las=0,pl,pr;
    while(q--){
        // cin>>l>>r;
        l=readin(1ll),r=readin(1ll);
        if(opt){
            l=(l^las)%M+1,r=(r^las)%M+1;
            if(l>r)swap(l,r);
        }--l;
        pl=lower_bound(w_arr+1,w_arr+m+1,l)-w_arr;
        if(pl>m)pl=m;
        else if(w_arr[pl]>l)--pl;
        pr=lower_bound(w_arr+1,w_arr+m+1,r)-w_arr;
        if(pr>m)pr=m;
        else if(w_arr[pr]>r)--pr;
        las=g[pr]+f[pr]-g[pl]-f[pl]+(r-w_arr[pr])*f[pr]-(l-w_arr[pl])*f[pl];
        // cout<<las<<'\n';
        writc(las,'\n');
    }
}

signed main(){
    // freopen("sample.in","r",stdin);
    // freopen("shit.out","w",stdout);
    Init();
    Get_G();
    Get_hash();
    Dijkstra();
    Get_query();
    return 0;
}