有图有真相

· · 题解

竞选本题最简单做法，有图有真相。

先求 a_i 的前缀和，以下 a_i 都指前缀和数组。为了省略下标加减，下文所有统计答案过程向左偏移一位。

扫描极好区间 (l,r] 的右端点 r，则支配的左端点 (l,a_l) 形成了一个单调降的序列：

case 1

考虑队尾到 r 的红色部分，这一段操作为 \operatorname{chkmx}([tail,r),a_r-a_{tail})，容易发现随着右端点减小，左端点单调不增，直接用单调队列维护这个操作。

case 2

考虑不为队尾的部分，这里每个点支配的区间固定，则转而求其在队列期间的 \max\left\{a_r\right\}，设 nxt_i=\min_{i\le j\wedge a_j\le a_i}\left\{j\right\} 不存在设为 n，先求出每个点的支配区间 [i,nxt_i)，明显这个可以通过单调栈一次求出。

直接放松限制，忽略某点被偏序的情况，区间 [i,nxt_i) 在队列中的必要条件为 r-R\le i\wedge nxt_i\le r-L，而贡献即 \max_{j\in [nxt_i+L,i+R]}\left\{a_j\right\}-a_i，ST 表求区间最值即可。

所有 [i,nxt_i) 区间是无交叉关系的（除包含无交），可直接建树处理，dfn 序恰好是 1\to n，扫一遍的时候和 fa_i 取 \max 即可。

总复杂度 \mathcal{O}(nq+n\log n)。

#include "bits/stdc++.h"
using namespace std;
#define pii pair<int,int>
#define pli pair<ll1,int>
#define pil pair<int,ll1>
#define mkp make_pair
#define fir first
#define sec second
typedef unsigned long long ll2;
typedef long long ll1;
const ll1 inf=1e18;
const int N=5e4+5;
ll1 a[N],mx[16][N],ans[N];
int fa[N],b[N],nxt[N],Log2[N],K1=0,n,q,L,R;
pii prs[N];pli mn[16][N];
set<int>S;set<int>::iterator iter,iter1,iter2;
bool cmpa(int x,int y){return a[x]==a[y]?x>y:a[x]<a[y];}
bool cmplen(pii x,pii y){return x.sec-x.fir<y.sec-y.fir;}
void init(){
    Log2[0]=Log2[1]=0;
    for(int i=1;i<=n;i++){
        Log2[i]=Log2[i-1];
        if(i==(1<<(Log2[i]+1)))Log2[i]++;
    }
    for(int i=1;i<=n;i++)
        mx[0][i]=a[i],mn[0][i]=mkp(a[i-1],i-1);
    for(int k=1;(1<<k)<=n;k++)for(int i=1;i+(1<<k)-1<=n;i++){
        mx[k][i]=max(mx[k-1][i],mx[k-1][i+(1<<(k-1))]);
        mn[k][i]=min(mn[k-1][i],mn[k-1][i+(1<<(k-1))]);
    }
    S.clear();S.insert(n);
    for(int i=0;i<n;i++)b[i]=i;
    sort(b,b+n,cmpa);
    for(int o=0;o<n;o++){
        int i=b[o];iter=S.insert(i).fir;
        nxt[i]=*(++iter);
    }
    S.clear();
    for(int i=0;i<n;i++)prs[i]=mkp(i,nxt[i]-1);
    sort(prs,prs+n,cmplen);
    for(int o=0;o<n;o++){
        auto [l,r]=prs[o];
        iter1=S.lower_bound(l),iter2=S.upper_bound(r);
        for(iter=iter1;iter!=iter2;iter++)fa[*iter]=l;
        S.erase(iter1,iter2);S.insert(l),fa[l]=-1;
    }
}
ll1 qrymx(int l,int r){
    if(l>r)return -inf;
    K1=Log2[r-l+1];return max(mx[K1][l],mx[K1][r-(1<<K1)+1]);
}
pli qrymn(int l,int r){
    if(l>r)return mkp(inf,inf);
    K1=Log2[r-l+1];return min(mn[K1][l],mn[K1][r-(1<<K1)+1]);
}
pil que[N];
int hd=0,tl=0;
void solve(){
    for(int i=1;i<=n;i++)ans[i]=-inf;
    for(int i=0;i<n;i++){
        int lt=nxt[i]+L,rt=min(n,i+R);
        ans[i+1]=qrymx(lt,rt)-a[i];
        if(fa[i]!=-1)
            ans[i+1]=max(ans[i+1],ans[fa[i]+1]);
    }
    hd=1,tl=0;
    for(int i=n;i>=1;i--){
        if(i>=L){
            auto [alt,Lt]=qrymn(max(1,i-R+1),i-L+1);Lt++;
            while(hd<=tl){
                if(que[tl].sec<=a[i]-alt)tl--;
                else break;
            }
            que[++tl]=mkp(Lt,a[i]-alt);
        }
        while(hd<=tl){
            if(que[hd].fir>i)hd++;
            else break;
        }
        if(hd<=tl)ans[i]=max(ans[i],que[hd].sec);
    }
    ll2 tmp,Ans=0;
    for(ll2 i=1;i<=n;i++)
        tmp=ans[i],Ans=(Ans^(tmp*i));
    printf("%llu\n",Ans);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]),a[i]+=a[i-1];
    init();
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&L,&R);
        solve();
    }
    return 0;
}