题意

给定一个长度为 \(n\) 的排列，有 \(q\) 次询问，每次询问一个区间 \([l,r]\) ，找到最小的包含 \([l,r]\) 的区间，满足这个区间包含了一段连续的数字。

\(n\leq 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能够到达的最小最大的标号 ，再将每个位置得到的限制放到线段树里查询即可。

• 容易证明一个区间的答案可以用上述方式构造。因为如果 \(a\leq b\leq c\leq d\) ，同时 \([a,c],[b,d]\) 是本征区间,那么 \([b,c],[a,d]\) 也是本征区间，可以考虑反证。

• 总时间复杂度为 \(O(nlogn)\)。

代码

#include
    
     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_backinline 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
     
      inline bool Max(T &a,T b){return a
      
       
        inline bool Min(T &a,T b){return b
        
         >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
         
          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\n",l,r); continue; } data res=t[1].query(l+1,r,1,n,1); printf("%d %d\n",res.l,res.r); } return 0;}