题目链接

题意分析

首先对于一个区间[L,R] 可以发现:Max-Min+L-R=0

如果你不知道该怎么维护的话 请看看这道题

现在关键是 对于一个区间怎么维护

首先可以证明的是 一个字串的本征区间是唯一的

因为两个区间的交也是区间 所以两个区间都包含这个区间的话 那么二者的交符合条件而且是更优的

所以我们直接针对长度求最优就可以了

首先 我们把所有的询问子串按照右端点排序 然后进行扫描 扫到的加入一个堆里 按照左端点从大到小进行排序 堆顶的是左端点最大的子串

然后 我们使用线段树维护当前函数 \(f(x)=Max-Min+l-r\) 维护答案的最小值 以及整个最小值最靠右的位置 因为当前右端点确定 所以我们肯定希望左端点尽可能的向右

对于当前堆顶的元素也就是子串 如果说子串的左端点往左存在符合要求的点的话 那么就是我们要求的点

疑点：

1.如果对于一个子串来说 后面存在更优的怎么办？

假设说对于当前的子串求得的本征区间为[L1,R1] 但是实际上对应有更优的L2,R2

那么由于因为两个区间的交也是区间 所以实际上会有更优的[L2,R1]

2.如果堆顶的子串一直找不到答案 那么会不会耽误堆里其他的子串找到答案？

不会有这种情况发生的

你们认为会耽误的只有这种情况

但是为什么会耽误呢?

我们是按照右端点顺序加入堆的 在堆顶元素入堆之前还没有找到答案出堆的话 堆顶的本征区间一定被堆下面子串的本征区间包含的

所以我们就可以好好求了

CODE:

#include
#include
#include
#include
#include
#include
#include
#define N 100080
#define inf 2147483600
using namespace std;
int n,m,tpx,tpy;
int num[N],stx[N],sty[N];
int ansl[N],ansr[N];
struct Node
{
	int le,ri,id;
	friend bool operator < (const Node &A,const Node &B)
	{return A.le==B.le ? A.ri que;
struct Tree
{
	int Min,nowat,tag;
}tre[N<<2];
bool cmp(const Node &A,const Node &B)
{return A.ri==B.ri ? A.le>1;
	build(now<<1,le,mid);build(now<<1|1,mid+1,ri);
	pushup(now);
}
void update(int now,int lenow,int rinow,int le,int ri,int d)
{
	if(le<=lenow&&rinow<=ri)
	{
		tre[now].Min+=d;
		tre[now].tag+=d;
		return;
	}
	if(tre[now].tag) down(now);
	int mid=(lenow+rinow)>>1;
	if(le<=mid) update(now<<1,lenow,mid,le,ri,d); 
	if(mid query(int now,int lenow,int rinow,int le,int ri)
{
	if(le<=lenow&&rinow<=ri) return make_pair(tre[now].Min,tre[now].nowat);
	if(tre[now].tag) down(now);
	int mid=(lenow+rinow)>>1;pair tmp1=make_pair(inf,0),tmp2=make_pair(inf,0);
	if(le<=mid) tmp1=query(now<<1,lenow,mid,le,ri);
	if(mid>n;
	for(int i=1;i<=n;++i) cin>>num[i];
	cin>>m;
	for(int i=1,x,y;i<=m;++i)
	{
		cin>>x>>y;qe[i]=(Node){x,y,i};
	}
//	sort(qe+1,qe+m+1);
//	for(int i=1;i<=m;++i)
//	printf("[%d] = (%d %d)\n",i,qe[i].le,qe[i].ri);
	sort(qe+1,qe+m+1,cmp);build(1,1,n);
//	for(int i=1;i<=m;++i)
//	printf("[%d] = (%d %d)\n",i,qe[i].le,qe[i].ri);	
//	for(int i=1;i<=n;++i) printf("%d%c",query(1,1,n,i,i).first,(i==n ? '\n':' '));
	for(int i=1,tail=1;i<=n;++i)
	{
//		printf("now at %d\n",i);
		update(1,1,n,1,n,-1);
//for(int i=1;i<=n;++i) printf("%d%c",query(1,1,n,i,i).first,(i==n ? '\n':' '));		
		while(tail<=m&&qe[tail].ri<=i)
		que.push(qe[tail++]);
		while(tpx&&num[stx[tpx]]num[i])
		update(1,1,n,sty[tpy-1]+1,sty[tpy],num[sty[tpy]]-num[i]),--tpy;
		sty[++tpy]=i;			
//		printf("che2\n");
		while(!que.empty())
		{
			Node tmp=que.top();
//			printf("now is %d\n",tmp.id); 
			int bian=tmp.le;
//			printf("cdy\n");
			pair nowtmp=query(1,1,n,1,bian);		
			if(nowtmp.first==0) 
			{
				ansl[tmp.id]=nowtmp.second;
				ansr[tmp.id]=i;
				que.pop();
			}
			else break;
		}
//		printf("check3\n");
	}
	for(int i=1;i<=m;++i) printf("%d %d\n",ansl[i],ansr[i]);
	return 0;	
}