首先不考虑 w(每条边的难度)的数据范围,我们可以得到以下的做法。
预处理:
- 用 spfa 求出 dis[i],表示:从 x 到每一个点的路径上,最大难度的最小值
- 用 addp[i] (一个 vector)存储:牛半仙的困难接受程度从 i-1 增加到 i 的时候,他能见到的新的妹子们。
将 i 号节点 push 到 addp[dis[i]] 里。
- 计算一个 ans 数组,其 ans[i] 表示:在牛半仙的困难接受程度为 i 的时候,他一次出行能见到几种妹子
开一个桶,i 从 0 扫到 W_max,每一次将 addp[i] 中的节点加到桶中,看是否是新增的类别
- 预处理一下前缀和,用一个数组 anssum[i] 表示。
离散化
可惜这题的 w 非常大,所以必须先进行离散化,pool[i] 表示 i 在离散化之前的值,此数组已经排过序。
于是 ans 数组的定义变为:
在牛半仙的困难接受程度为 pool[i] 的时候,他一次出行能见到几种妹子
不难发现,牛半仙的困难接受程度在 pool[i]~pool[i+1]-1 之间的时候,答案都是相同的。
所以,anssum(前缀和)数组的定义变为:
计算方法也发生了改变:
但是要求的 l,r 不一定正好在 pool 中,所以要求的长度为 i 前缀和也不一定恰好是 anssum 的某一项,所以实现了一个函数 cal_ans 来计算精确的前缀和,如下:
inline long long cal_ans(long long diff){ diff++; long long idx=lower_bound(pool+1,pool+1+pcnt,diff)-pool; if(pool[idx]>diff)idx--; return anssum[idx]+(diff-pool[idx])*ans[idx]; }
除了 spfa 之外复杂度 ,而这题不卡spfa,故neng'g。
全部代码
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> using namespace std; //ll const int MXN=5e5+5; const int MXM=MXN<<1; const int MXC=605; const long long INF=1e18; long long p; long long n,m,q,x,opt; long long head[MXN],ter[MXM],nxt[MXM],wei[MXM],ecnt=0; long long c[MXN],pool[MXN],pcnt=0; long long dis[MXN]; bool inq[MXN]; vector<long long> addp[MXN]; inline void ae(long long ts,long long tt,long long tw){ nxt[++ecnt]=head[ts];head[ts]=ecnt; ter[ecnt]=tt;wei[ecnt]=tw; } inline void spfa(){ memset(dis,0x3f,sizeof(dis)); dis[x]=0; queue<long long> q; q.push(x); while(!q.empty()){ long long cur=q.front(); q.pop(); inq[cur]=0; for(long long i=head[cur];i;i=nxt[i]){ long long nx=ter[i]; if(max(dis[cur],wei[i])<dis[nx]){ dis[nx]=max(dis[cur],wei[i]); if(!inq[nx]){ inq[nx]=1; q.push(nx); } } } } for(long long i=1;i<=n;i++){ long long pl=lower_bound(pool+1,pool+1+pcnt,dis[i])-pool; addp[pl].push_back(i); } } bool hasc[MXC]; long long ans[MXN],anssum[MXN]; inline long long cal_ans(long long diff){ diff++; long long idx=lower_bound(pool+1,pool+1+pcnt,diff)-pool; if(pool[idx]>diff)idx--; return anssum[idx]+(diff-pool[idx])*ans[idx]; } int main(){ scanf("%lld%lld%lld%lld%lld",&n,&m,&q,&x,&opt); if(opt==1)scanf("%lld",&p); for(long long i=1;i<=n;i++)scanf("%lld",&c[i]); for(long long i=1;i<=m;i++){ long long ts,tt,tw; scanf("%lld%lld%lld",&ts,&tt,&tw); pool[++pcnt]=tw; ae(ts,tt,tw); ae(tt,ts,tw); } //加几项便于处理 pool[++pcnt]=0; pool[++pcnt]=INF; sort(pool+1,pool+1+pcnt); pcnt=unique(pool+1,pool+1+pcnt)-pool-1; spfa(); for(int i=1;i<=pcnt;i++){ ans[i]=ans[i-1]; anssum[i]=anssum[i-1]+ans[i-1]*(pool[i]-pool[i-1]); for(int j=0;j<(int)addp[i].size();j++) if(!hasc[c[addp[i][j]]]){ ans[i]++; hasc[c[addp[i][j]]]=1; } } long long last=0; while(q--){ long long l,r; scanf("%lld%lld",&l,&r); if(opt){ l=(l^last)%p+1; r=(r^last)%p+1; if(l>r)swap(l,r); } printf("%lld\n",last=(cal_ans(r)-cal_ans(l-1))); } return 0; }