这类问题是有一个排列，若一个区间的值域也是连续的，那么称它是一个连续段，然后问一些相关问题。
连续段有一些显然的性质。
- 若 是连续段且 交集非空，则 都是连续段。若还满足互不包含，则它们的差集也是连续段。
[CERC2017]Intrinsic Interval
给定一个长度为 的排列， 次询问，每次给定 求包含 的最短连续段。
经典例题。暑假纪中就考过，但是题解给了一个 的分治做法。
离线做法
首先分析一下包含一个区间的连续段，如果有两个连续段都包含了这个区间，那么它们的交一定也包含这个连续段，而且根据上面的性质交也是连续段。这样就推出包含一个区间的最短连续段一定是可行的段中右端点最靠左的。
那么我们就考虑离线，考虑每个右端点。如何判定一个区间是否是连续段？考虑值域连续的性质，如果把每个 都连边的话，其实等价于 的生成子图中有 条边。即 。那么我们把每个点的初值设为 ，再去维护 到 的 ，如果这个位置的值等于 那么就是一个连续段。而 只可能更小，所以等于 的就是最大值。那么维护区间最大值，查询时线段树上二分即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int n,m,a[N],mx[N*4],laz[N*4],p[N],L[N],R[N];
struct node{int l,r,id;bool operator <(const node &b)const{return l<b.l;}}q[N];
priority_queue<node>pq;
bool cmp(node a,node b){return a.r<b.r;}
void build(int x,int l,int r){
if(l==r){mx[x]=l;return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
mx[x]=max(mx[x<<1],mx[x<<1|1]);
}
void down(int x){
int L=x<<1,R=x<<1|1,&d=laz[x];
mx[L]+=d;laz[L]+=d;mx[R]+=d;laz[R]+=d;d=0;
}
void change(int x,int l,int r,int ql,int qr){
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){mx[x]++;laz[x]++;return;}
int mid=(l+r)>>1;down(x);
change(x<<1,l,mid,ql,qr);change(x<<1|1,mid+1,r,ql,qr);
mx[x]=max(mx[x<<1],mx[x<<1|1]);
}
int query(int x,int l,int r,int qr,int d){
if(mx[x]<d||l>qr)return 0;
if(l==r)return l;down(x);
int mid=(l+r)>>1,dat=query(x<<1|1,mid+1,r,qr,d);
if(!dat)dat=query(x<<1,l,mid,qr,d);
return dat;
}
int main(){
scanf("%d",&n);build(1,1,n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),p[a[i]]=i;
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp);
for(int i=1,j=0;i<=n;i++){
if(a[i]>1&&p[a[i]-1]<i)change(1,1,n,1,p[a[i]-1]);
if(a[i]<n&&p[a[i]+1]<i)change(1,1,n,1,p[a[i]+1]);
while(j<m&&q[j+1].r<=i)pq.push(q[++j]);
while(pq.size()){
node x=pq.top();int d=query(1,1,n,x.l,i);
if(d)L[x.id]=d,R[x.id]=i,pq.pop();else break;
}
}
for(int i=1;i<=m;i++)printf("%d %d\n",L[i],R[i]);
return 0;
}
在线做法
如果询问区间长度为 ，那么答案就是它本身，否则，一定会包含一些长度为 的区间。
考虑这些长度为 的区间。如果答案中包含 这个区间，那么 这些数都应该出现。这像是一个选某元素就必须选某元素的模型，可以建好图之后缩SCC解决。然后发现这个连边方式就是点向区间连边。所以线段树优化建图。但是最后需要求一个点可以到达多少点，这个很难求。不过这种连边方式（点向包含自己的区间连边）决定了最后能到达的点也是一段区间。于是记录 即可。处理询问时就询问这区间内左端点最小值和右端点最大值即可。
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=1e5+50,inf=1e9,M=N*3;
int n,m,a[N],lc[M],rc[M],cnt,rt,dfn[M],low[M],st[M],tp,bel[M],scc,clk;bool ins[M];
struct node{int mn,mx;node operator +(const node &b){return node{min(mn,b.mn),max(mx,b.mx)};}}t[N*4],dat[N*4],dd[M];
vector<int>v[M],vv[M];
void build(int x,int l,int r){
if(l==r){t[x]=dat[l];return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
t[x]=t[x<<1]+t[x<<1|1];
}
node query(int x,int l,int r,int ql,int qr){
if(l>qr||r<ql)return node{inf,-inf};
if(l>=ql&&r<=qr)return t[x];
int mid=(l+r)>>1;
return query(x<<1,l,mid,ql,qr)+query(x<<1|1,mid+1,r,ql,qr);
}
void build2(int &x,int l,int r){
if(l==r){x=l;return;}
int mid=(l+r)>>1;x=++cnt;
build2(lc[x],l,mid);build2(rc[x],mid+1,r);
v[x].pb(lc[x]);v[x].pb(rc[x]);
}
void change(int x,int l,int r,int ql,int qr,int d){
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){v[d].pb(x);return;}
int mid=(l+r)>>1;
change(lc[x],l,mid,ql,qr,d);
change(rc[x],mid+1,r,ql,qr,d);
}
void cmin(int &x,int y){y<x?x=y:0;}
void cmax(int &x,int y){y>x?x=y:0;}
void tarjan(int x){
dfn[x]=low[x]=++clk;st[++tp]=x;ins[x]=1;
for(int i=0,y;i<v[x].size();i++)
if(!dfn[y=v[x][i]])tarjan(y),cmin(low[x],low[y]);
else if(ins[y])cmin(low[x],dfn[y]);
if(dfn[x]==low[x]){
int y;scc++;
do y=st[tp--],ins[y]=0,bel[y]=scc,vv[scc].pb(y);while(y!=x);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),dat[a[i]]=node{i,i};
build(1,1,n);cnt=n-1;build2(rt,1,n-1);
for(int i=1;i<n;i++){
node x=query(1,1,n,min(a[i],a[i+1]),max(a[i],a[i+1]));
change(rt,1,n-1,x.mn,x.mx-1,i);
}
tarjan(rt);
for(int i=1;i<=scc;i++){
dd[i].mn=inf;dd[i].mx=-inf;
for(int j=0,x;j<vv[i].size();j++){
if((x=vv[i][j])<n)cmin(dd[i].mn,x),cmax(dd[i].mx,x+1);
for(int k=0,y;k<v[x].size();k++)
if(bel[y=v[x][k]]!=i)dd[i]=dd[i]+dd[bel[y]];
}
}
for(int i=1;i<n;i++)dat[i]=dd[bel[i]];build(1,1,n);
scanf("%d",&m);
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&l,&r);
if(l==r)printf("%d %d\n",l,r);
else{
node x=query(1,1,n,l,r-1);
printf("%d %d\n",x.mn,x.mx);
}
}
return 0;
}
析合树做法
对于一个连续段，如果不存在与它相交但没有相互包含关系的连续段，则它被成为本原段。
可以发现所有本原段之间形成树形结构，析合树就是这个树形结构。
析合树的节点分为析点和合点。
析点的性质为任意一段连续的儿子构成的序列不是连续段。
合点性质为任意一段连续的儿子构成的序列都是连续段。
根据本原段的定义，可以发现所有的连续段，要么是一个析点，要么是合点的一段连续的儿子。（比较显然）
那么构建出析合树之后，对于询问 ，找到这两个点的 lca，如果是析点那就是它，如果是合点那就是它向下伸出的两个儿子。所以关键就是构建析合树。
增量构建。用栈维护当前森林最右端的链。关键地方看注释咯。
#include<bits/stdc++.h>
#define L x<<1
#define R x<<1|1
#define M ((l+r)>>1)
#define pb push_back
using namespace std;
const int N=2e5+50;
int n,m,a[N],p[N],mn[20][N],mx[20][N],lo[N],t[N*4],laz[N*4],ll[N],rr[N],f[N][20],cnt,st[N],tp,is_he[N],mm[N],rt,d[N],id[N];
vector<int>v[N];
int read(){
int x=0,c;
while(!isdigit(c=getchar()));
while(isdigit(c))x=x*10+c-48,c=getchar();
return x;
}
int gmx(int l,int r){
int p=lo[r-l+1];
return max(mx[p][l],mx[p][r-(1<<p)+1]);
}
int gmn(int l,int r){
int p=lo[r-l+1];
return min(mn[p][l],mn[p][r-(1<<p)+1]);
}
bool chk(int l,int r){return gmx(l,r)-gmn(l,r)==r-l;}//ST表查一下这个区间是否为连续段
void build(int x,int l,int r){
if(l==r){t[x]=l;return;}
build(L,l,M);build(R,M+1,r);
t[x]=max(t[L],t[R]);
}
void mdf(int x,int d){t[x]+=d;laz[x]+=d;}
void down(int x){
if(laz[x])mdf(L,laz[x]),mdf(R,laz[x]),laz[x]=0;
}
void change(int x,int l,int r,int ql,int qr){
if(l>qr||r<ql)return;
if(l>=ql&&r<=qr){mdf(x,1);return;}
down(x);
change(L,l,M,ql,qr);change(R,M+1,r,ql,qr);
t[x]=max(t[L],t[R]);
}
int query(int x,int l,int r,int d){
if(t[x]<d)return 0;
if(l==r)return l;down(x);
int ret=query(L,l,M,d);
if(!ret)ret=query(R,M+1,r,d);
return ret;
}
void dfs(int x){
d[x]=d[f[x][0]]+1;
for(int i=0;i<17;i++)f[x][i+1]=f[f[x][i]][i];
for(int i=0,y;i<v[x].size();i++)f[y=v[x][i]][0]=x,dfs(y);
}
int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
for(int i=17;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i];
if(x==y)return x;
for(int i=17;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
int Son(int x,int y){
for(int i=17;~i;i--)if(d[f[y][i]]>d[x])y=f[y][i];
return y;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)mn[0][i]=mx[0][i]=a[i]=read(),p[a[i]]=i;
for(int i=2;i<=n;i++)lo[i]=lo[i>>1]+1;
for(int i=1;i<=16;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]),
mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
build(1,1,n);
for(int i=1;i<=n;i++){
if(a[i]>1&&p[a[i]-1]<i)change(1,1,n,1,p[a[i]-1]);
if(a[i]<n&&p[a[i]+1]<i)change(1,1,n,1,p[a[i]+1]);
int l=query(1,1,n,i),now=++cnt;id[i]=now;//l是以i为右端点的连续段最靠左的左端点
ll[now]=rr[now]=i;// 这里的 L,R 是指值域的上下界
while(tp&&l<=ll[st[tp]]){
if(is_he[st[tp]]&&chk(mm[st[tp]],i))// 判断是否能成为儿子，如果能就做（给合点再加一个儿子）
v[st[tp]].pb(now),rr[st[tp]]=i,now=st[tp--];
else if(chk(ll[st[tp]],i)){// 合点一定是被这样建出来的
is_he[++cnt]=1;v[cnt].pb(st[tp]);v[cnt].pb(now);
ll[cnt]=ll[st[tp--]];rr[cnt]=i;
mm[cnt]=ll[now];now=cnt;//这里M数组的作用是保证合点的性质
}
else{//构建一个析点。这里就是我们需要数据结构维护的原因。我们需要知道是否存在这么一个析点。
v[++cnt].pb(now);now=cnt;
// 如果从当前结点开始不能构成连续段，就合并。
// 直到找到一个结点能构成连续段。而且我们一定能找到这样一个节点
while(!chk(ll[st[tp]],i))v[cnt].pb(st[tp--]);
ll[cnt]=ll[st[tp]];rr[cnt]=i;v[cnt].pb(st[tp--]);
}
}
st[++tp]=now;
}
dfs(rt=st[1]);scanf("%d",&m);
for(int i=1,l,r;i<=m;i++){
scanf("%d%d",&l,&r);
int x=id[l],y=id[r],z=lca(x,y);
if(is_he[z])printf("%d %d\n",ll[Son(z,x)],rr[Son(z,y)]);
else printf("%d %d\n",ll[z],rr[z]);
}
return 0;
}
关于这个数据结构维护，有两种思路。本代码是上面“离线做法”中的那种思路，即维护生成子图中的边数的思路。这样较简单。传统的做法中是根据连续段 的性质，维护这个值的最小值。还需要用两个单调栈辅助修改，比较麻烦。
三种做法切爆此题hhh
还有一些性质...析点的儿子个数至少 个（否则不可能满足析点的性质），且儿子个数大于等于 个的析点都有可能存在（2,4,6...n,1,3,5...或 4,6,8...n-1,1,3,5...n,2）。
然后给一些资料的链接吧。构建非排列的析合树，用到析合树的生成函数题/jk，构建析合树的数据结构维护部分（前置技能）， 构建的方法