Range | Sum | Maximum 题解

Gold14526 · 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;
}