自动搬运

查看原文

来自洛谷，原作者为

	ZnPdCo 「是不是糖的都无所谓了」

搬运于2025-08-24 23:02:13，当前版本为作者最后更新于2024-08-09 07:15:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

发现 $|S_x\cup S_y|=|S_x|+|S_y|-|S_x\cap S_y|$，前面两项容易通过前缀和计算，所以我们只需要求出最后一项就好了。发现 $|S_x\cap S_y|=\min_{i=x}^{y-1} |S_i|-1$，证明不难理解，就是从后往前做单调栈时，单调栈内元素最少的一刻就是两集合的交。

所以现在我们的问题就变成了求：

$$(\sum_{l\le x\le y\le r} \min_{i=x}^{y-1}|S_i|-1)-(\sum_{\substack{{1\le x<l}\\{r<y\le r}}} \min_{i=x}^{y-1}|S_i|-1) $$

定义 $L_i=\sum_{1\le x < y\le i} \min_{i=x}^{y-1}|S_i|$，$R_i=\sum_{i\le x < y\le n} \min_{i=x}^{y-1}|S_i|$。

考虑怎么快速计算上述的值，可以考虑每加入一个数对答案的贡献，发现 $L_i$ 比 $L_{i-1}$ 多了一个以 $i$ 为右端点的贡献，分为对比他大的区间的贡献与比他小的区间的贡献，用单调栈即可维护。

根据容斥，上述式子的值为 $L_r+R_l-L_n$。

综上，总复杂度 $O(n)$。

#include <bits/stdc++.h>
#define N 10000010
#define P 998244353
#define ll long long
using namespace std;
namespace IO{
	const int sz=1<<22;
	char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
	inline char gc(){
		return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
	}
	template<class T> void read(T& x){
		x=0; char c=gc();
		for(;c<'0'||c>'9';c=gc());
		for(;c>='0'&&c<='9';c=gc())
			x=x*10+(c-'0');
	}
	inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
	inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
	template<class T> void write(T x,char c='\n'){
		if(x<0) pc('-'), x=-x;
		if(x==0) pc('0'); int t=0;
		for(;x;x/=10) p[++t]=x%10+'0';
		for(;t;--t) pc(p[t]); pc(c);
	}
	struct F{~F(){flush();}}f;
}
using IO::read;
using IO::write;
int n, c, q, a[N], nxt[N], f[N], sta[N], top;
ll L[N], R[N], sum, s[N], X;
int main() {
	read(n), read(X), read(c);
	for(int i = 1; i <= n; i ++) {
		a[i] = i;
	}
	for(int i = 1; i <= c; i ++) {
		int l, r;
		l = (X * (X ^ i)) % n + 1;
		r = (X ^ (1ll * i * i)) % n + 1;
		swap(a[l], a[r]);
	}
	top = 0, sta[top] = n + 1;
	for(int i = n; i >= 1; i --) {
		while(top && a[sta[top]] < a[i]) top --;
		nxt[i] = sta[top];
		sta[++ top] = i;
	}
	for(int i = n; i >= 1; i --)
		f[i] = 1 + f[nxt[i]];
	for(int i = 1; i <= n; i ++)
		s[i] = (s[i - 1] + f[i]) % P;
	top = 0, sta[top] = 0;
	for(int i = 1; i < n; i ++) {
		while(top && f[sta[top]] > f[i]) {
			sum -= 1ll * (f[sta[top]] - 1) * (sta[top] - sta[top - 1]) % P;
			sum = (sum % P + P) % P;
			top --;
		}
		sum += 1ll * (f[i] - 1) * (i - sta[top]) % P;
		sum = (sum % P + P) % P;
		sta[++ top] = i;
		L[i] = (L[i - 1] + sum) % P;
	}
	top = 0, sum = 0, sta[top] = n;
	for(int i = n - 1; i >= 1; i --) {
		while(top && f[sta[top]] > f[i]) {
			sum -= 1ll * (f[sta[top]] - 1) * (sta[top - 1] - sta[top]) % P;
			top --;
		}
		sum += 1ll * (f[i] - 1) * (sta[top] - i) % P;
		sum = (sum % P + P) % P;
		sta[++ top] = i;
		R[i] = (R[i + 1] + sum) % P;
	}
	read(q);
	ll res = 0;
	for(ll i = 1; i <= q; i ++) {
		int l, r;
		l = min((X * i + (X ^ (X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
		r = max((X * i + (X ^ (X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
		ll ans = (s[r] - s[l - 1]) * (r - l) % P - 
			s[l - 1] * (n - r) % P - 
			(s[n] - s[r]) * (l - 1) % P - 
			(L[r - 1] + R[l] - L[n - 1]) % P +
		(s[r] - s[l - 1]) % P;
		ans = (ans % P + P) % P;
		res ^= ans;
	}
	write(res);
}