牛客第三场提高组模拟赛T2题解

~~队里除了我都炸了~~

$$ n,m \leq 5\times 10^5,q \leq 10^5,c_i\leq 600, 0首先不考虑 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] 表示。

$$anssum[i]=\sum_{i=1}^{i-1} ans[i]$$

离散化

可惜这题的 w 非常大，所以必须先进行离散化，pool[i] 表示 i 在离散化之前的值，此数组已经排过序。

于是 ans 数组的定义变为：

在牛半仙的困难接受程度为 pool[i] 的时候，他一次出行能见到几种妹子

不难发现，牛半仙的困难接受程度在 pool[i]~pool[i+1]-1 之间的时候，答案都是相同的。

所以，anssum（前缀和）数组的定义变为：

计算方法也发生了改变：

$$ \begin{aligned} anssum[i]&=\sum_{j=1}^{i-1} ans[j-1]\times(pool[j]-pool[j-1])\cr &=anssum[i-1]+ans[i-1]*(pool[i]-pool[i-1]) \end{aligned} $$

但是要求的 l，r 不一定正好在 pool 中，所以要求的长度为 i 前缀和也不一定恰好是 anssum 的某一项，所以实现了一个函数 cal_ans 来计算精确的前缀和，如下：

1
2
3
4
5
6


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 之外复杂度 $O(n+m+q)$，而这题不卡 spfa ，故能过。

全部代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102


#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;
}