自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:35:23，当前版本为作者最后更新于2022-08-01 09:44:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷 P8037 题解

$\text{Link}$

思路分析

好题，考虑对询问离线并按右端点排序

我们先考虑右端点是最大值的情况，反过来的只需要对每个数取反再做一次

记录每个点为区间左端点能够达到最远的右端点

考虑加入新的一个点 $a_r$，那么我们需要更新某一段区间 $[l,r]$ 中的数的右端点为 $r$，其中 $l$ 为满足 $l\le r$ 且 $a_{l-1}>a_r$ 的最大整数

为了快速求出 $l$，我们可以维护一个递减的单调栈

接下来考虑 $[l,r]$ 区间内有哪些点的右端点可以被更新为 $r$，假设某个点 $a_x$ 的右端点可以被更新为 $r$，当且仅当：

那么如果加入 $a_r$，每一个满足 $a_x> a_r$ 的点以后就一直不能被更新了，所以我们再维护一个递增的单调栈，每次弹栈弹掉的这些元素就不能再更新右端点

考虑对以上操作用线段树维护以下信息：

• 维护当前区间可以使 $r$ 作为右端点并形成合法区间的第一个点，如果没有则设为 $0$
• 每个点作为左端点能获得的最大区间长度的最大值
• 区间更新右端点的 LazyTag

注意那些不能更新右端点的点依然可能对答案做出贡献

时间复杂度 $\Theta(n\log n)$

总结：

离线按右端点排序是处理区间问题的一个常用 trick（就是不知道本题强制在线怎么做。。。）

把所有数取反再跑一遍的 trick 看起来好像也还挺高妙的

有些区间问题可以固定右端点然后考虑左端点的贡献，这个做法好像我还没见过

一些实现的细节请看代码

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
int n,m;
class SegmentTree {
	private:
		struct node {
			int pos,len,tag;
			/*
			 * pos: 当前最左合法左端点 
			 * len: 当前区间最大长度
			 * tag: 区间更新右端点的懒标记 
			 */
		}	tree[MAXN<<2];
		inline int left(int x) {
			return x<<1;
		}
		inline int right(int x) {
			return x<<1|1;
		}
		inline void pushup(int pos) {
			tree[pos].len=max(tree[left(pos)].len,tree[right(pos)].len);
			tree[pos].pos=(!tree[left(pos)].pos)?tree[right(pos)].pos:tree[left(pos)].pos;
		}
		inline void pushdown(int pos) {
			//用pos作为右端点更新两个区间的最大长度 
			if(!tree[pos].tag) return ;
			tree[left(pos)].tag=max(tree[left(pos)].tag,tree[pos].tag);
			tree[right(pos)].tag=max(tree[right(pos)].tag,tree[pos].tag);
			if(tree[left(pos)].pos) {
				tree[left(pos)].len=max(tree[left(pos)].len,tree[pos].tag-tree[left(pos)].pos+1);
			}
			if(tree[right(pos)].pos) {
				tree[right(pos)].len=max(tree[right(pos)].len,tree[pos].tag-tree[right(pos)].pos+1);
			}
			tree[pos].tag=0;
		}
	public:
		inline void Build(int l=1,int r=n,int pos=1) {
			if(l==r) {
				tree[pos].pos=tree[pos].len=tree[pos].tag=0;
				return ;
			}
			int mid=(l+r)>>1;
			Build(l,mid,left(pos));
			Build(mid+1,r,right(pos));
			pushup(pos);
		}	
		inline void ModifyL(int u,int k,int l=1,int r=n,int pos=1) {
			//修改左端点是否合法 
			if(l==r) {
				tree[pos].pos=k;
				return ;
			}
			pushdown(pos);
			int mid=(l+r)>>1;
			if(u<=mid) ModifyL(u,k,l,mid,left(pos));
			else ModifyL(u,k,mid+1,r,right(pos));
			pushup(pos);
		}
		inline void ModifyR(int ul,int ur,int k,int l=1,int r=n,int pos=1) {
			//区间修改右端点 
			if(ul<=l&&r<=ur) {
				if(tree[pos].pos) tree[pos].len=max(tree[pos].len,k-tree[pos].pos+1);
				tree[pos].tag=max(tree[pos].tag,k);
				return ;
			}
			pushdown(pos);
			int mid=(l+r)>>1;
			if(ul<=mid) ModifyR(ul,ur,k,l,mid,left(pos));
			if(mid<ur) ModifyR(ul,ur,k,mid+1,r,right(pos));
			pushup(pos);
		}
		inline int Query(int ql,int qr,int l=1,int r=n,int pos=1) {
			if(ql<=l&&r<=qr) return tree[pos].len;
			pushdown(pos);
			int mid=(l+r)>>1,res=0;
			if(ql<=mid) res=max(res,Query(ql,qr,l,mid,left(pos)));
			if(mid<qr) res=max(res,Query(ql,qr,mid+1,r,right(pos)));
			return res;
		}
}	S;
struct query {
	int l,id;
};
vector <query> q[MAXN];
int st1[MAXN],st2[MAXN],a[MAXN],ans[MAXN];
inline void solve() {
	st1[0]=st2[0]=0; //单调栈栈顶 
	S.Build();
	for(int i=1;i<=n;++i) {
		while(st1[0]&&a[st1[st1[0]]]<=a[i]) --st1[0];
		int l=st1[st1[0]]+1;
		st1[++st1[0]]=i;
		while(st2[0]&&a[st2[st2[0]]]>a[i]) {
			S.ModifyL(st2[st2[0]],0);
			//这个点以后都不能更新新的右端点了 
			--st2[0];
		}
		st2[++st2[0]]=i;
		S.ModifyL(i,i);
		S.ModifyR(l,i,i);
		for(auto qry:q[i]) {
			ans[qry.id]=max(ans[qry.id],S.Query(qry.l,i));
		}
	}
}
signed main() {
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;++i) {
		int l,r;
		scanf("%d%d",&l,&r);
		q[r].push_back((query){l,i});
	}
	solve();
	for(int i=1;i<=n;++i) a[i]*=-1;
	solve();
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0;
}