题意
给定一个长度为 (n) 的排列，有 (q) 次询问，每次询问一个区间 ([l,r]) ，找到最小的包含 ([l,r]) 的区间，满足这个区间包含了一段连续的数字。
(nleq 10^5)
分析
-
考虑相邻的两个位置 (i,i+1)，记两个位置的值为 $ x ,y(x< y)$ 如果要出现在答案里，要满足 (val in[x,y]) 都出现。
-
用权值线段树维护一段权值区间出现位置的最左最右端 ([l,r])，显然位置 (p in[l,r]) 都要在区间中，线段树优化建边，表示在 (i,i+1) 出现时 ([l,r]) 也要出现。
-
求强联通分量之后求出每个scc能够到达的最小最大的标号 ，再将每个位置得到的限制放到线段树里查询即可。
-
容易证明一个区间的答案可以用上述方式构造。因为如果 (aleq bleq cleq d) ，同时 ([a,c],[b,d]) 是本征区间,那么 ([b,c],[a,d]) 也是本征区间，可以考虑反证。
-
总时间复杂度为 (O(nlogn))。
代码
#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].lst,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
inline int gi(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=4e5 + 7,inf=0x3f3f3f3f;
int n,m,a[N];
#define Ls o<<1
#define Rs o<<1|1
struct data{
int l,r;
data(){l=inf;}data(int l,int r):l(l),r(r){}
data operator +(const data &rhs)const{
return data(min(l,rhs.l),max(r,rhs.r));
}
};
struct sgt{
data t[N];
void pushup(int o){
t[o]=t[Ls]+t[Rs];
}
void modify(int p,int l,int r,int o,data v){
if(l==r){
t[o]=v;
return;
}int mid=l+r>>1;
if(p<=mid) modify(p,l,mid,Ls,v);
else modify(p,mid+1,r,Rs,v);
pushup(o);
}
data query(int L,int R,int l,int r,int o){
if(L<=l&&r<=R) return t[o];
int mid=l+r>>1;
if(R<=mid) return query(L,R,l,mid,Ls);
if(L>mid) return query(L,R,mid+1,r,Rs);
return query(L,R,l,mid,Ls)+query(L,R,mid+1,r,Rs);
}
}t[2];
int head[N],pos[N],edc;
struct edge{
int lst,to;
edge(){}edge(int lst,int to):lst(lst),to(to){}
}e[N*30];
void Add(int a,int b){
e[++edc]=edge(head[a],b),head[a]=edc;
}
void build(int l,int r,int o){
if(l==r) {
pos[l]=o;
return;
}
int mid=l+r>>1;
Add(o,Ls);Add(o,Rs);
build(l,mid,Ls);
build(mid+1,r,Rs);
}
void modify(int L,int R,int l,int r,int o,int v){
if(L<=l&&r<=R) { Add(v,o); return;}
int mid=l+r>>1;
if(L<=mid) modify(L,R,l,mid,Ls,v);
if(R>mid) modify(L,R,mid+1,r,Rs,v);
}
vector<int>G[N];
int low[N],pre[N],st[N],scc[N],tp,tim,scc_cnt;
int vis[N];
data t1[N],t2[N];
void tarjan(int u){
low[u]=pre[u]=++tim,st[++tp]=u;
go(u){
if(!low[v]){
tarjan(v);
Min(pre[u],pre[v]);
}else if(!scc[v]) Min(pre[u],low[v]);
}
if(low[u]==pre[u]&&++scc_cnt)
for(int x=-1;x^u;)
scc[x=st[tp--]]=scc_cnt;
}
void dfs(int u){
if(vis[u]) return;
vis[u]=1;
for(auto v:G[u]){
dfs(v);
t2[u]=t2[u]+t2[v];
}
}
int main(){
n=gi();
rep(i,1,n) a[i]=gi();
rep(i,1,n) t[0].modify(a[i],1,n,1,data(i,i));
build(1,n,1);
rep(i,2,n){
int x=min(a[i-1],a[i]),y=max(a[i-1],a[i]);
t1[ pos[i] ]=t[0].query(x,y,1,n,1);
modify(t1[ pos[i] ].l+1,t1[ pos[i] ].r,1,n,1,pos[i]);
}
rep(i,1,N-1) if(!scc[i]) tarjan(i);
rep(u,1,N-1) go(u) if(scc[u]^scc[v]) G[scc[u]].pb(scc[v]);
rep(i,1,N-1) t2[scc[i]]=t2[scc[i]]+t1[i];
rep(i,1,scc_cnt) dfs(i);
rep(i,2,n) t[1].modify(i,1,n,1,t2[scc[pos[i]]]);
int q=gi();
while(q--){
int l=gi(),r=gi();
if(l==r) { printf("%d %d
",l,r); continue; }
data res=t[1].query(l+1,r,1,n,1);
printf("%d %d
",res.l,res.r);
}
return 0;
}