自动搬运

查看原文

来自洛谷，原作者为

	Gold14526 nothing

搬运于2025-08-24 23:16:00，当前版本为作者最后更新于2025-03-27 21:13:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发现区间 $[l,r]$ 的权值等于区间 $[l-1,r]$ 中最大的前缀和减去最小的前缀和。

于是问题转化为求出所有长度为 $k$ 的区间最大值和。

这个就比较套路了，对于每个前缀和 $s_i$，我们用单调栈求出其作为最大值的极长区间 $[l_i,r_i]$，设 $\Delta l=i-l_i+1,\Delta r=r_i-i+1,len=r_i-l_i+1$，不妨假设 $\Delta l\le \Delta r$，那么它对答案有以下贡献：

• 对于 $i\in[1,\Delta l]$，它对 $ans_i$ 有 $i\times s_i$ 的贡献。
• 对于 $i\in(\Delta l,\Delta r]$，它对 $ans_i$ 有 $\Delta l\times s_i$ 的贡献。
• 对于 $i\in(\Delta r,len]$ 它对 $ans_i$ 有 $(len-i+1)\times s_i$ 的贡献。

发现是区间加等差数列的形式，两次差分即可解决。

注意区间 $[l,r]$ 长度比 $[l-1,r]$ 长度小 $1$，所以上述的贡献的区间左右端点都要减一，或者最后要把 $ans_i$ 替换成原来的 $ans_{i+1}$。

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
int read()
{
	int x=0,zf=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')zf=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch-'0');
		ch=getchar();
	}
	return x*zf;
}
void print(cll x)
{
	if(x<10)
	{
		putchar(x+'0');
		return;
	}
	print(x/10);
	putchar(x%10+'0');
}
void princh(cll x,const char ch)
{
	print(x);
	putchar(ch);
}
cint N=1e6;
int n,a[N+1],l[N+1],r[N+1];
ll s[N+1],ans[N+3];
struct stck{
	int a[N+1],t;
	void clear(cint x){a[0]=x,t=0;}
	void push(cint x){a[++t]=x;}
	void pop(){--t;}
	int top(){return a[t];}
	int size(){return t;}
	bool empty(){return (t==0);}
}st;
void calc()
{
	st.clear(-1);
	for(int i=0;i<=n;++i)
	{
		while(!st.empty()&&s[st.top()]<=s[i])st.pop();
		l[i]=st.top()+1;
		st.push(i);
	}
	st.clear(n+1);
	for(int i=n;i>=0;--i)
	{
		while(!st.empty()&&s[st.top()]<s[i])st.pop();
		r[i]=st.top()-1;
		st.push(i);
	}
	for(int i=0;i<=n;++i)
	{
		int p=i-l[i]+1,q=r[i]-i+1;
		if(p>q)swap(p,q);
		ans[0]+=s[i];
		ans[p]-=s[i];
		ans[q]-=s[i];
		ans[r[i]-l[i]+2]+=s[i];
	}
}
void solve()
{
	n=read();
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		s[i]=s[i-1]+a[i];
		ans[i]=0;
	}
	ans[0]=0;
	calc();
	for(int i=0;i<=n;++i)
	{
		s[i]=-s[i];
	}
	calc();
	for(int i=1;i<=n;++i)
	{
		ans[i]+=ans[i-1];
	}
	ll res=0;
	for(int i=1;i<=n;++i)
	{
		ans[i]+=ans[i-1];
		res^=ans[i]%(1ll*i*i);
	}
	princh(res,'\n');
}
int main()
{
	int T=read();
	while(T--)solve();
	return 0;
}