题目概述

Luogu4747

解题报告

找性质题过于困难……

首先很明显，如果两个合法区间有重叠部分，那重叠部分一定也是合法的。更进一步，根据这个性质可以得知答案一定是唯一的，否则两个答案区间的重叠部分一定是更短的答案。

也就是说，在所有包含 $[L,R]$ 的合法区间 $[l,r]$ 中，最短的不仅 $l$ 最大，$r$ 也是最小的。

有了这个性质就可以得出这么一个离线算法：从左往右维护一个数据结构，支持查询以 $i$ 结尾的区间中哪些是合法区间，然后对于询问 $[L,R]$ ，在 $i=R$ 时把 $L$ 加入大根堆中。每次以 $i$ 结尾时，查询堆顶 $L$ ，找到最大的 $l\le L$ 满足 $[l,i]$ 是合法的，则 $[L,R]$ 的答案就是 $[l,i]$。

现在唯一的问题就是这个数据结构，不难发现线段树是可以维护的，维护方法有两种：

1. 对于 $l$ ，合法条件为 $\max_{l\le j\le i}a_j-\min_{l\le j\le i}a_j\le i-l$ ，单调栈+线段树区间修改维护。
2. 求区间内 $a,a+1$ 的对数 $cnt_{l,i}$ ，合法条件为 $cnt_{l,i}\ge i-l$ ，每次加 $i$ 时对 $a_i-1,a_i+1$ 位置区间修改维护。

第二种较为好写。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100000,maxt=maxn<<2;

int n,a[maxn+5],pos[maxn+5];
int m,L[maxn+5],R[maxn+5],ansL[maxn+5],ansR[maxn+5];
vector<int> e[maxn+5];
int MAX[maxt+5],tag[maxt+5],res;
int si,Heap[maxn+5];

void Build(int l,int r,int p=1){
    if (l==r) {MAX[p]=l;return;}
    int mid=l+(r-l>>1);
    Build(l,mid,p<<1);Build(mid+1,r,p<<1|1);
    MAX[p]=max(MAX[p<<1],MAX[p<<1|1]);
}
inline void Addtag(int p,int k) {tag[p]+=k;MAX[p]+=k;}
void Pushdown(int p) {if (tag[p]) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=0;}
void Insert(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l && r==R) return Addtag(p,k);
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Insert(L,R,k,l,mid,p<<1); else if (L>mid) Insert(L,R,k,mid+1,r,p<<1|1);
    else Insert(L,mid,k,l,mid,p<<1),Insert(mid+1,R,k,mid+1,r,p<<1|1);
    MAX[p]=max(MAX[p<<1],MAX[p<<1|1]);
}
void Find(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l && r==R){
        if (MAX[p]<k) return;
        if (l==r) {res=l;return;}
        int mid=l+(r-l>>1);Pushdown(p);
        MAX[p<<1|1]>=k?Find(mid+1,R,k,mid+1,r,p<<1|1):Find(L,mid,k,l,mid,p<<1);
        return;
    }
    int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Find(L,R,k,l,mid,p<<1); else if (L>mid) Find(L,R,k,mid+1,r,p<<1|1); else {
        Find(mid+1,R,k,mid+1,r,p<<1|1);
        if (res) return;
        Find(L,mid,k,l,mid,p<<1);
    }
}
inline bool cmp(const int &i,const int &j) {return L[i]<L[j];}
#define Push(x) (Heap[++si]=(x),push_heap(Heap+1,Heap+1+si,cmp))
#define Pop() (pop_heap(Heap+1,Heap+1+si--,cmp))
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
    scanf("%d",&m);
    for (int i=1;i<=m;i++) scanf("%d%d",&L[i],&R[i]),e[R[i]].push_back(i);
    Build(1,n);
    for (int i=1;i<=n;i++){
        if (1<a[i] && pos[a[i]-1]<i) Insert(1,pos[a[i]-1],1);
        if (a[i]<n && pos[a[i]+1]<i) Insert(1,pos[a[i]+1],1);
        for (auto x:e[i]) Push(x);
        while (si){
            int x=Heap[1];
            res=0;Find(1,L[x],i);
            if (!res) break;
            ansL[x]=res;ansR[x]=i;
            Pop();
        }
    }
    for (int i=1;i<=m;i++) printf("%d %d\n",ansL[i],ansR[i]);
    return 0;
}