uoj213 【UNR #1】争夺圣杯

题目

设(f_i)表示所有长度为(i)的区间的最大值的和，求(igoplus sum_{i=1}^nf_i)

不难发现随机数据非常好做

由于一个随机序列的前缀最大值期望只会变化(log)次，所以完全可以从这个条件上入手

考虑维护一个合并式单调栈，每次插入一个数之后，单调栈中存在的都是当前这个前缀所有的后缀最大值，我们直接暴力扫一遍这些后缀最大值，于是有一些针对(f)数组的区间加，我们直接差分维护就好了

这样在数据随机意义下是(O(nlog n))的，一发跑过了除了( m hack)数据以外的所有数据也是非常惊人

考虑正解，使用单调栈找到一个位置(i)左边第一个小于等于他的(j)，和右边第一个大于他的(k)，显然在左端点在([j,i])内，右端点在([i,k))的区间的最大值都是(a_i)，于是直接讨论一下(a_i)对这些长度区间的贡献就好了

设(a=min(i-j+1,k-i),b=max(i-j+1,k-i))

对于长度为([1,a])的区间，贡献是(x imes a_i)

对于长度为([a+1,b])的区间，贡献是(b imes a_i)

对于长度为([b+1,a+b-1])的区间，贡献为((b-x) imes a_i=b imes a_i-x imes a_i)

维护两个差分数组，一个用于维护这个位置实际上增加了多少，一个用于维护这个位置增加了多少倍的(x)

随便就做完了，复杂度是(O(n))的

代码

#include<bits/stdc++.h>
#define re register
#define LL long long
inline int read() {
	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int mod=998244353;
const int maxn=1e6+5;
int a[maxn],pre[maxn],mn[maxn],t[maxn],st[maxn],c[maxn];
int n,top;LL ans;
inline void calc(int pos) {
	int a=t[top]-mn[top]+1,b=pos-t[top]+1;
	if(a>b) std::swap(a,b);
	int v=st[top]%mod;
	if(a<b) {
		pre[a+1]=(pre[a+1]+1ll*a*v%mod)%mod;
		pre[b+1]=(pre[b+1]-1ll*a*v%mod+mod)%mod;
	}
	c[1]=(c[1]+v)%mod,c[a+1]=(c[a+1]-v+mod)%mod;
	if(b<a+b-1) {
		c[b+1]=(c[b+1]-v+mod)%mod,c[a+b]=(c[a+b]+v)%mod;
		pre[b+1]=(pre[b+1]+1ll*(a+b)*v%mod)%mod;
		pre[a+b]=(pre[a+b]-1ll*(a+b)*v%mod+mod)%mod;
	}
}
int main() {
	n=read();for(re int i=1;i<=n;++i) a[i]=read();top=0;
	for(re int i=1;i<=n;i++) {
		int now=i;
		while(top&&a[i]>=st[top]) calc(i-1),now=mn[top],top--;
		mn[++top]=now,t[top]=i,st[top]=a[i];
	}
	while(top) calc(n),top--;
	for(re int i=1;i<=n;i++) pre[i]=(pre[i-1]+pre[i])%mod;
	for(re int i=1;i<=n;i++) c[i]=(c[i-1]+c[i])%mod;
	for(re int i=1;i<=n;i++) 
		pre[i]=(pre[i]+1ll*c[i]*i%mod)%mod,ans^=pre[i];
	printf("%lld
",ans);
}