有图有真相

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

先求

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)

。

CPP

#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;
}

文章操作

case 1

case 2

相关推荐

评论

有图有真相