题意
给定长为 \(n\) 的序列 \(a\)，\(q\) 次询问 \(L,R\)，你需要对每个 \(i\) 求出长度在 \([L,R]\) 之间且包含 \(i\) 的所有子段中 \(a_i\) 和最大是多少。
\(n\le 5\times10^4,q\le 2^{10}\)
分析
考虑到暴力必须要用单调队列维护，不出意外这题正解肯定要用到单调队列。思考怎么用单调队列做。
假设单调队列里已经维护了若干个权值递降的区间 \([l,r]\)，将权值变成前缀和形式 \(s_r-s_{l-1}\)，显然一个 \(r\) 此时只有一个 \(l\) 是有用的。对于一个 \(i\)，我们会有如下操作：
- 弹出 \(r<i\) 的区间。
- 加入 \([i,i+R-1]\)。
- 将满足 \(i+L-1\le r\) 且 \(s_{l-1}\ge s_{i-1}\) 的 \(l\) 替换成 \(i\)。
首先容易想到将 \(i+L-1\le r\) 和 \(i+L-1>r\) 两种情况分别维护单调队列，这样第一个单调队列就少了一个限制。第二个单调队列的维护（没有第三个操作）和第一个单调队列的前两个操作是平凡的，不再赘述；对于第三个操作，分析一下单调队列的性质，首先显然有 \(r\) 递增、权值递降，其次我们需要发现，\(s_{l-1},l\) 的值均递增，这是因为如果存在单调队列后面的 \(l\) 比前面更小而值更小，那么由于这两个 \(l\) 两者都能取到，那么将两个 \(l\) 替换成最优的那个 \(l\) 一定不劣，\(s_{l-1}\) 也一样。
所以第一个单调队列里形成了若干个 \(s_{l-1}\) 相同的连续段。我们不妨改为维护 \(s_{l-1}\) 的单调队列，每个值内部在维护一个单调队列，替换 \(l\) 的过程就是合并两个单调队列的过程，即，将前面的单调队列的一段没用的后缀弹掉，然后将后面的单调队列全部搬过去。发现我们实际上只需要维护删除和连接操作，用链表维护并记录开头和结尾即可。
实现上，发现二操作实际上可以和三操作合并，即我们提前给 \(i\) 的链表加入一个 \(i+R-1\) 然后在合并单调队列即可。复杂度显然是 \(O(nq)\) 的。
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<numeric>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<array>
#include<tuple>
#include<ctime>
#include<random>
#include<cassert>
#include<chrono>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define j0 jj0
#define j1 jj1
#define y0 yy0
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0)
#define OTIE cout.tie(0)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define deb(val) cerr<<#val<<'='<<val<<','
#define debl(val) cerr<<#val<<'='<<val<<'\n'
#define lowb lower_bound
#define uppb upper_bound
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define un using namespace
#define il inline
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof x)
#define popc __builtin_popcountll
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) ((x)&-(x))
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
//#define double long double
#define int long long
//#define int __int128
using namespace std;
using namespace __gnu_pbds;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
template<typename T1,typename T2>inline bool ckmx(T1 &qwqx,T2 qwqy){return qwqx>=qwqy?0:(qwqx=qwqy,1);}
template<typename T1,typename T2>inline bool ckmn(T1 &qwqx,T2 qwqy){return qwqx<=qwqy?0:(qwqx=qwqy,1);}
inline auto rd(){int qwqx=0,qwqf=1;char qwqch=getchar();while(qwqch<'0'||qwqch>'9'){if(qwqch=='-')qwqf=-1;qwqch=getchar();}while(qwqch>='0'&&qwqch<='9'){qwqx=(qwqx<<1)+(qwqx<<3)+qwqch-48;qwqch=getchar();}return qwqx*qwqf;
}
template<typename T>inline void write(T qwqx,char qwqch='\n'){if(qwqx<0){qwqx=-qwqx;putchar('-');}int qwqy=0;static char qwqz[40];while(qwqx||!qwqy){qwqz[qwqy++]=qwqx%10+48;qwqx/=10;}while(qwqy--){putchar(qwqz[qwqy]);}if(qwqch)putchar(qwqch);
}
bool Mbg;
const int mod=998244353;
template<typename T1,typename T2>inline void adder(T1 &x,T2 y){x+=y,x=x>=mod?x-mod:x;}
template<typename T1,typename T2>inline void suber(T1 &x,T2 y){x-=y,x=x<0?x+mod:x;}
const int maxn=5e4+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int n,Q;
int a[maxn];
int st[maxn],ed[maxn];
int lft[maxn],rht[maxn];
deque<int>q1;
deque<pii>q2;
inline void solve_the_problem(){n=rd();rep(i,1,n)a[i]=a[i-1]+rd();Q=rd();while(Q--){rep(i,1,n)st[i]=ed[i]=lft[i]=0,rht[i]=n+1;int L=rd(),R=rd();q1.clear(),q2.clear();int mx=a[R],lst=R;st[1]=ed[1]=R;per(i,R-1,L)if(ckmx(mx,a[i]))lft[lst]=i,rht[i]=lst,st[1]=i,lst=i;q1.push_back(1);auto ins=[&](pii x)->void{while(!q2.empty()&&q2.back().fi<=x.fi)q2.pop_back();q2.push_back(x);};auto calc=[&](){int res=-llinf;if(!q1.empty())ckmx(res,a[st[q1.front()]]-a[q1.front()-1]);if(!q2.empty())ckmx(res,q2.front().fi);return res;};u64 ans=calc();rep(i,2,n){while(!q1.empty()){int id=q1.front(),p;for(p=st[id];p<=n;p=rht[p]){if(i+L-1>p)ins(mp(a[p]-a[id-1],p));else break;}if(p<=n){st[id]=p,lft[p]=0;break;}q1.pop_front();}while(!q2.empty()&&q2.front().se<i)q2.pop_front();auto merge=[&](int x,int y)->void{while(ed[x]&&a[st[y]]>=a[ed[x]])ed[x]=lft[ed[x]];if(!ed[x])return;lft[st[y]]=ed[x],rht[ed[x]]=st[y],st[y]=st[x];};if(i+R-1<=n){st[i]=ed[i]=i+R-1;}else if(!q1.empty()&&a[i-1]<=a[q1.back()-1]){st[i]=st[q1.back()],ed[i]=ed[q1.back()];q1.pop_back();}if(st[i]){while(!q1.empty()&&a[i-1]<=a[q1.back()-1])merge(q1.back(),i),q1.pop_back();int val=a[st[i]]-a[i-1];while(!q1.empty()){int id=q1.back(),p;for(p=ed[id];p&&val>a[p]-a[id-1];p=lft[p]);if(p){ed[id]=p,rht[p]=n+1;break;}q1.pop_back();}q1.push_back(i);}ans^=1ull*i*calc();}write(ans);}
}
bool Med;
signed main(){
// freopen(".in","r",stdin);freopen(".out","w",stdout);fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);int _=1;while(_--)solve_the_problem();
}
/**/