https://www.luogu.org/blog/ywycasm/solution-p4747#
这种“好的区间”，见得还是比较多的了。
mx-mi=r-l
比较经典的题是统计这样的区间个数。可以分治+大力分类讨论mx，mi的位置
但是这个题是一个询问。
先观察一些显而易见的性质：
1.好的区间的交也是好的区间
2.好的区间的并也是好的区间
所以，考虑对于一个询问，如果往后固定r找到了一个[L,R]的L左边最靠后的l，使得[l,r]是好区间，那么这就是最优答案了。后面再有也一定是包含关系。
固定r的话，不如试试离线扫描线？
用set存询问，L大到小排序。不合法直接break，因为更小的区间更不可能有左端点。合法更新答案，然后erase
问题在于，当r变成r+1的时候，我们怎样快速维护每个li的位置是不是有[li,r+1]是一个好的区间
一个比较棒的转化是:
如果[l,r]是一个好的区间，那么把这个区间的数排序之后，得到的序列相邻两项相差一定是1
定义(i,j)为一个好的二元组，当且仅当a[i]-a[j]=1
这样的两项的二元组在[l,r]中恰好有r-l个
所以，一个区间是好的区间，当且仅当好的二元组有r-l个。
线段树每个位置维护到r的二元组个数val
val+l=r则l位置是好的区间
l不变，不妨线段树位置初值为下标。
更新的话，设p[i]为权值为i的数的数组下标
多了一个a[r]，对于左端点位于[1,p[a[r]-1]]和[1,p[a[r]+1]]的到r都会多一个二元组！
所以这些位置区间+1
存在val+l=r的找最右边的l？
发现tmp=val+l，最大就是r！（因为val最多就是r-l）
所以区间最大值最右边的那一个位置。
线段树随便搞
#include<bits/stdc++.h> #define reg register int #define mid ((l+r)>>1) #define ls (x<<1) #define rs (x<<1|1) #define il inline #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=100000+5; int n,m; int a[N],p[N]; struct po{ int mx,id; po(){} po(int vv,int dd){ mx=vv,id=dd; } bool friend operator <(po a,po b){ if(a.mx!=b.mx) return a.mx<b.mx; return a.id<b.id; } }pr; struct node{ po v; int ad; }t[4*N]; void pushup(int x){ t[x].v=max(t[ls].v,t[rs].v); } void pushdown(int x){ if(!t[x].ad) return; t[ls].v.mx+=t[x].ad; t[ls].ad+=t[x].ad; t[rs].v.mx+=t[x].ad; t[rs].ad+=t[x].ad; t[x].ad=0; } void build(int x,int l,int r){ if(l==r){ t[x].v=po(l,l); t[x].ad=0; return; } build(ls,l,mid); build(rs,mid+1,r); pushup(x); } void add(int x,int l,int r,int L,int R,int c){ if(L<=l&&r<=R){ t[x].ad+=c; t[x].v.mx+=c; return; } pushdown(x); if(L<=mid) add(ls,l,mid,L,R,c); if(mid<R) add(rs,mid+1,r,L,R,c); pushup(x); } po query(int x,int l,int r,int L,int R){//ask the rightest mx's pos if(L<=l&&r<=R) return t[x].v; pushdown(x); po ret;ret.mx=-2333,ret.id=-6666; if(L<=mid) ret=max(ret,query(x<<1,l,mid,L,R)); if(mid<R) ret=max(ret,query(x<<1|1,mid+1,r,L,R)); return ret; } struct que{ int l,r,id; bool friend operator <(que a,que b){ if(a.l!=b.l) return a.l>b.l; if(a.r!=b.r) return a.r>b.r; return a.id<b.id; } }q[N]; bool cmp(que a,que b){ return a.r<b.r; } pair<int,int>ans[N]; set<que>s; set<que>::iterator it; int main(){ rd(n); for(reg i=1;i<=n;++i) rd(a[i]),p[a[i]]=i; rd(m); for(reg i=1;i<=m;++i){ rd(q[i].l);rd(q[i].r); q[i].id=i; } sort(q+1,q+m+1,cmp); build(1,1,n); int ptr=1; for(reg i=1;i<=n;++i){ while(ptr<=m&&q[ptr].r==i){ s.insert(q[ptr]);++ptr; } if(a[i]>1&&p[a[i]-1]<i) add(1,1,n,1,p[a[i]-1],1); if(a[i]<n&&p[a[i]+1]<i) add(1,1,n,1,p[a[i]+1],1); while(s.size()){ que now=*s.begin(); pr=query(1,1,n,1,now.l); if(pr.mx!=i){ break; } ans[now.id].first=pr.id; ans[now.id].second=i; s.erase(now); } } for(reg i=1;i<=m;++i){ printf("%d %d ",ans[i].first,ans[i].second); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/25 19:27:07 */
（mx-mi=r-l l+mx-mi=r，这个是不可以维护的，因为第一不好维护，第二没有最大值就是r的限制，不能查找）
总结：
离线+扫描线是处理区间询问的利器
尤其这个题，r对l的贡献又相对独立，而且可以支持快速单点增量改变，所以扫描线处理起来就游刃有余。
好区间的交、二元组的性质也是重要的思维过程。
upda：2019.3.17：主要还是利用二元组的转化思想，使得贡献独立