专栏文章

NOIP T4 怎么把一个暴力改改直接变正解

IIvanZhang2009
P14638题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mimybykw
此快照首次捕获于
2025/12/01 17:33
3 个月前
此快照最后确认于
2025/12/01 17:33
3 个月前
查看原文
首先需要会一个分治的 O(nlog⁡n)O(n\log n) 单次询问做法，膜拜感谢这篇题解。
简单讲就是一次询问给定了 L,RL,R，我们 solve(x,y) 解决 x≤l≤i≤r≤yx\le l\le i\le r\le y 的问题（[l,r][l,r] 是题目中长度 [L,R][L,R] 的区间）。我们假设 i≤midi\le mid，那枚举 ll，要求 r>midr>mid 且 r−l+1∈[L,R]r-l+1\in[L,R]，这样可行的 rr 是区间，对于每个 ll 可以单调队列求出来。然后每个左端点的 ll 的答案可以贡献到 [l,mid][l,mid] 的 ii 上，做一个前缀 max⁡\max 即可。然后右边同理。这样一个子问题的时间复杂度是 O(min⁡(R,r−l+1))O(\min(R,r-l+1))（注意这个 RR 的 checkmin 哦）。然后显然区间长度 <L<L 就可以停。
然后考虑一个很深刻的事情：如果 RL=O(1)\frac RL=O(1)，那只有 O(nL)O(\frac nL) 个区间会被分治到，那么复杂度就是 O(nLR)=O(n)O(\frac nLR)=O(n)。
我们考虑把询问的限制分成 log⁡n\log n 段：[2i,2i+1−1][2^i,2^{i+1}-1]。每个询问可以拆成 O(log⁡n)O(\log n) 个整段和两个散段。注意每个小段内 RL≤2\frac RL\le 2，分治是 O(n)O(n) 的，所以散块暴力。对于整块，我们预处理每个整块每个数的答案，查询的时候相当于每个 ii 查询第 ljl_j 到 rjr_j 个块的答案，相当于大小为 log⁡n\log n 的 RMQ，直接随便做。
时间复杂度 O(nlog⁡nlog⁡log⁡n+nq)O(n\log n\log\log n+nq)。看代码理应很好理解。可惜应该是被卡常了。
分治可以是线性的，很深刻吧！
CPP
#include<bits/stdc++.h>
using namespace std;
#define int         long long
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
int n,q;
int a[200005],b[200005],c[200005];
int L,R;
int Q[200005];
void solve(int l,int r){
	if(r-l+1<L)return;
	if(l==r){
		c[l]=max(c[l],a[l+1]-a[l]);
		return;
	}
	int m=(l+r)>>1;
	solve(l,m);solve(m+1,r);
	int x=m+1,f1=0,f2=-1;
	int mx=-1e18;
	REP(i,max(l,m+1-R+1),m+1){
		int ll=max(m+1,i+L-1),rr=min(r,i+R-1);
		if(ll>rr){
			c[i]=max(c[i],mx);
			continue;
		}
		while(x<=rr){
			while(f1<=f2&&a[Q[f2]+1]<a[x+1])--f2;
			Q[++f2]=x;
			++x;
		}
		while(f1<=f2&&Q[f1]<ll)++f1;
		mx=max(mx,a[Q[f1]+1]-a[i]);
		c[i]=max(c[i],mx);
	}
	x=m;f1=0,f2=-1;mx=-1e18;
	for(int i=min(r,m+R-1);i>m;--i){
		int ll=max(l,i-R+1),rr=min(m,i-L+1);
		if(ll>rr){
			c[i]=max(c[i],mx);
			continue;
		}
		while(x>=ll){
			while(f1<=f2&&a[Q[f2]]>a[x])--f2;
			Q[++f2]=x;
			--x;
		}
		while(f1<=f2&&Q[f1]>rr)++f1;
		mx=max(mx,a[i+1]-a[Q[f1]]);
		c[i]=max(c[i],mx);
	}
}
int pc[50004][18][18];
void Main(){
	cin>>n;
	REP(i,0,n)cin>>a[i+1],a[i+1]+=a[i];
	cin>>q;
	int m=1;
	for(int j=1;(1<<j)<=n;++j){
		++m;
		REP(i,0,n)c[i]=-1e18;
		int ll=(1<<j),rr=(1<<(j+1))-1;rr=min(rr,n);
		L=ll;R=rr;
		solve(0,n-1);
		REP(i,0,n)pc[i][j][j]=c[i];
	}
	REP(i,0,n){
		REP(j,1,m){
			REP(l,j+1,m){
				pc[i][j][l]=max(pc[i][j][l-1],pc[i][l][l]);
			}
		}
	}
	#define ull unsigned long long
	REP(i,0,q){
		cin>>L>>R;
		REP(j,0,n)c[j]=L==1? a[j+1]-a[j]:-1e18;
		int Ll=m,Rr=-1;
		REP(j,1,m){
			int ll=(1<<j),rr=(1<<(j+1))-1;rr=min(rr,n);
			if(L<=ll&&rr<=R){
				Ll=min(Ll,j);Rr=max(Rr,j);
			}else if(ll<=R||rr>=L){
				int sl=L,sr=R;
				L=max(L,ll);R=min(R,rr);
				solve(0,n-1);
				L=sl;R=sr;
			}
		}
		if(Ll<=Rr){
			REP(j,0,n)c[j]=max(c[j],pc[j][Ll][Rr]);
		}
		ull ans=0;
		REP(j,0,n)ans^=(ull)(c[j])*(j+1);
		cout<<ans<<"\n";
	}
}
signed main(){
	cin.tie(0);ios::sync_with_stdio(0);
    int tc=1;
	while(tc--)Main();
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...