OI-Wiki

考虑这样一类问题：

给定一个排列 \(p_i\)，定义一个区间 \([l,r]\) 是好的，当且仅当 \(\cup{p_{l\cdots r}}\) 恰好为一段连续的数字。

多次询问一个区间的子区间中好的区间有几个。

这类问题应该有不止一种解法。而其中比较通用的一种就是析合树。

考虑上面那个问题。其实“好的区间”有一个专业点的词叫“连续段”。

比如 \(p=\{2,3,1,4,5\}\)，连续段有 \([1,1],[2,2],[3,3],[4,4],[5,5],[1,2],[1,3],[1,4],[4,5],[1,5]\)。

但是这样的连续段有 \(O(n^2)\) 个，不可能一个个求出来。

但是我们发现一些奇特的性质：比如上述 \([1,4],[4,5],[1,5]\) 是所有由端点在 \(\{1,4,5\}\) 构成的区间。而这些都是连续段。

所以我们考虑能不能建出一颗树。首先它应该是类似于线段树的样子，即每个节点代表一个线段。

但考虑上述的性质，我们希望它不一定是一个二叉树，而是希望它的某个节点的所有儿子恰好构成上述的“连续段集合”。

所以我们需要引入一个新的定义：本原段。

这个定义的数学表达可以去看 OI-Wiki。简单描述一下就是一类连续段，任何连续段与它们要么无交，要么包含。

比如 \(p=\{3,2,1,4\}\)，那么 \([1,3]\) 就是一个本原段，因为连续段 \([1,4]\) 包含 \([1,3]\)。\([4,4]\) 与 \([1,3]\) 无交，其余都被 \([1,3]\) 包含。

但是 \([1,2]\) 就不是一个本原段。虽然它是一个连续段，但是连续段 \([2,3]\) 与它有交且不是包含关系。

显然可以证明，任意一个长度大于1的本原段都可以分割成若干长度更小的本原段，两个本原段不存在交。所以本原段的个数是 \(O(n)\) 的。

然后我们规定：析合树上的所有节点都代表一个本原段。而且某个大于1的本原段是由其子节点合并而成。

我们规定一个子节点集合是：某个节点的所有子节点的区间构成的集合。比如 \(p=\{2,4,1,3\}\)，\([1,4]\) 的子节点集合就是 \(\{[1,1],[2,2],[3,3],[4,4]\}\)。其中 \([[3,3],[4,4]],[[1,1],[3,3]]\) 都是其中的子区间，对应的区间分别是 \([3,4],[1,3]\)。

而我们想要的“连续段集合”就是任取节点集合排序后的一个区间，它都是一个连续段。

但是我们发现，这里的“本原段”与我们上述希望的“连续段集合”有些时候不一定成立。

比如 \(p=\{2,4,1,3\}\)，长度大于1的连续段只有 \([1,4]\)，同样长度大于1的本原段也只有 \([1,4]\)。所以 \([1,1],[2,2],[3,3],[4,4]\) 都是 \([1,4]\) 的子节点。

但是显然并不存在所谓的“连续段集合”。所以我们需要修改一下定义。

我们发现，虽然上述的 \([1,4]\) 的子节点不能构成“连续段集合”，但是它有另一个性质：取其子节点集合中的任意一个子区间，只要区间里不止一个元素，所得到的的区间都不是连续段。

比如上述 \([1,4]\)，可以发现大小不为 1 和 4 的所有区间都不是连续段。

这样我们定义析合树上有两种节点：析点和合点（对应析合树）。

析点的性质：任取其子节点集合中的一个不止一个元素的子区间，所得到的的区间都不是连续段。

合点的性质：任取其子节点集合中的一个区间，所得到的的区间都是连续段。

可以证明，任何一个本原段不是合点就是析点。

特别的为了方便，我们认为所有长度为1的区间都对应析点。

那么接下来就是如何构造了。

考虑贪心构造。用一个栈，每次加入时首先把加入节点看做长度为1的区间。考虑有以下有几种情况：

1. 加入的节点可以直接塞入栈顶的子节点。直接处理
2. 加入的节点可以合并从栈顶起的若干个节点，形成一个合点。
3. 加入的节点可以合并从栈顶起的若干个节点（可以是0），形成一个析点。

对于 1,2 可以直接比较得出结果。但是 3 就比较麻烦了。

首先先引入一个很明显的用于判定的结论：一个区间是连续段当且仅当 \(\max\{p_{l\cdots r}\}-\min\{p_{l\cdots r}\}=r-l\)。

然后对于当前位置 \(i\)。我们希望维护这样一个数组 \(Q_j=\max\{p_{j\cdots i}\}-\min\{p_{j\cdots i}\}-(i-j)\)。

那么前面两个玩意用单调栈维护，后面那个用线段树维护。每次单调栈改变时顺便改变整体的值即可。

求出了这个东西，我们会发现：很明显当 \(Q_j=0\) 时一定存在一个区间满足条件。

那么我们找出最左端的那个位置 \(p'\)，不断合并上去。可以发现，无论是情况 2 还是情况 3，合并的最终位置都是 \(p'\)。

这样就可以做到均摊 \(O(n\log n)\) 的优秀复杂度。

至于统计 0 那就是常见套路了：处理区间最小值。由于这是一个排列，所以一定有 \(Q_j\geq 0\)。

[CERC2017]Intrinsic Interval

题目大意：多次询问求包含某段区间的最小长度连续段。

首先建出析合树，找到两个位置的LCA。如果这是一个析点，那么最后答案就是该点的区间。因为不存在一个更小的子区间是连续段了。

否则答案应该是对应两个子树的区间最大并。

即考虑定义：如果这是一个合点，任何一个子区间均是连续段，所以取包含 \(l\) 区间左端点和包含 \(r\) 的区间的右端点一定最优。

复杂度 \(O(n\log n)\)。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200010
using namespace std;
int num[N];
struct ST{
    int lg[N],al[N][18],ar[N][18];
    void init(int n)
    {
        lg[1]=0;
        for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++) al[i][0]=ar[i][0]=num[i];
        for(int i=1;i<=16;i++)
            for(int j=1;j+(1<<i)-1<=n;j++) al[j][i]=min(al[j][i-1],al[j+(1<<(i-1))][i-1]),ar[j][i]=max(ar[j][i-1],ar[j+(1<<(i-1))][i-1]);
    }
    int get_min(int l,int r){int t=lg[r-l+1];return min(al[l][t],al[r-(1<<t)+1][t]);}
    int get_max(int l,int r){int t=lg[r-l+1];return max(ar[l][t],ar[r-(1<<t)+1][t]);}
}st;
struct seg_tree{
    int val[N<<2],tag[N<<2];
    void set_tag(int u,int v){val[u]+=v;tag[u]+=v;}
    void push_down(int u)
    {
        if(!tag[u]) return;
        set_tag(u<<1,tag[u]),set_tag(u<<1|1,tag[u]),tag[u]=0;
    }
    void insert(int u,int l,int r,int L,int R,int v)
    {
        if(L<=l && r<=R){set_tag(u,v);return;}
        push_down(u);
        int mid=(l+r)>>1;
        if(L<=mid) insert(u<<1,l,mid,L,R,v);
        if(R>mid) insert(u<<1|1,mid+1,r,L,R,v);
        val[u]=min(val[u<<1],val[u<<1|1]);
    }
    int answer(int u,int l,int r)
    {
        if(l==r) return l;
        push_down(u);
        int mid=(l+r)>>1;
        if(!val[u<<1]) return answer(u<<1,l,mid);
        else return answer(u<<1|1,mid+1,r);
    }
}t;
int nxt[N<<1],to[N<<1],head[N],cnt;
void add(int u,int v)
{
    nxt[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
}
int fa[N][18],dep[N];
bool a_line(int l,int r){return st.get_max(l,r)-st.get_min(l,r)==r-l;}
int t1[N],tt1,t2[N],tt2;
int tn[N],tp;
int mn[N],id[N],lf[N],rf[N],typ[N],tot;
int build(int n)
{
    for(int i=1;i<=n;i++)
    {
        for(;tt1 && num[i]<=num[t1[tt1]];tt1--) t.insert(1,1,n,t1[tt1-1]+1,t1[tt1],num[t1[tt1]]);
        for(;tt2 && num[i]>=num[t2[tt2]];tt2--) t.insert(1,1,n,t2[tt2-1]+1,t2[tt2],-num[t2[tt2]]);
        t.insert(1,1,n,t1[tt1]+1,i,-num[i]);
        t.insert(1,1,n,t2[tt2]+1,i,num[i]);
        t1[++tt1]=t2[++tt2]=i;
        id[i]=++tot;lf[tot]=rf[tot]=i;
        int p=t.answer(1,1,n),u=tot;
        while(tp && lf[tn[tp]]>=p)
        {
            if(typ[tn[tp]] && a_line(mn[tn[tp]],i)){rf[tn[tp]]=i;add(tn[tp],u);u=tn[tp--];continue;}
            if(a_line(lf[tn[tp]],i))
            {
                typ[++tot]=1;
                lf[tot]=lf[tn[tp]],rf[tot]=i;mn[tot]=lf[u];
                add(tot,tn[tp--]),add(tot,u);
            }
            else
            {
                add(++tot,u);
                do add(tot,tn[tp--]); while(tp && !a_line(lf[tn[tp]],i));
                lf[tot]=lf[tn[tp]],rf[tot]=i;
                add(tot,tn[tp--]);
            }
            u=tot;
        }
        tn[++tp]=u;
        t.insert(1,1,n,1,i,-1);
    }
    return tn[1];
}
void dfs(int u,int p)
{
    fa[u][0]=p;
    dep[u]=dep[p]+1;
    for(int i=1;fa[u][i-1];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=nxt[i]) dfs(to[i],u);
}
int up(int x,int k)
{
    for(int i=17;i>=0;i--)
    if(k&(1<<i)) x=fa[x][i];
    return x;
}
int lca(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);x=up(x,dep[x]-dep[y]);
    if(x==y) return x;
    for(int i=17;i>=0;i--)
    if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&num[i]);
    st.init(n);
    int rt=build(n);
    dfs(rt,0);
    int m;
    scanf("%d",&m);
    while(m --> 0)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        int x=id[l],y=id[r];
        int c=lca(x,y);
        if(!x || !y || !c) throw;
        if(typ[c]) printf("%d %d\n",lf[up(x,dep[x]-dep[c]-1)],rf[up(y,dep[y]-dep[c]-1)]);
        else printf("%d %d\n",lf[c],rf[c]);
    }
    return 0;
}

CF526F Pudding Monsters

题目大意：\(n\times n\) 的棋盘上有 \(n\) 个棋子，保证行列互不相同。求有多少个正方形，使得其中每行每列都有棋子。

考虑转换题意：问有多少个区间，满足其数字连续。

这个就是析合树裸题了。复杂度 \(O(n\log n)\)。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 600010
using namespace std;
int num[N];
struct ST{
    int lg[N],al[N][19],ar[N][19];
    void init(int n)
    {
        lg[1]=0;
        for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++) al[i][0]=ar[i][0]=num[i];
        for(int i=1;i<=18;i++)
            for(int j=1;j+(1<<i)-1<=n;j++) al[j][i]=min(al[j][i-1],al[j+(1<<(i-1))][i-1]),ar[j][i]=max(ar[j][i-1],ar[j+(1<<(i-1))][i-1]);
    }
    int get_min(int l,int r){int t=lg[r-l+1];return min(al[l][t],al[r-(1<<t)+1][t]);}
    int get_max(int l,int r){int t=lg[r-l+1];return max(ar[l][t],ar[r-(1<<t)+1][t]);}
}st;
struct seg_tree{
    int val[N<<2],tag[N<<2];
    void set_tag(int u,int v){val[u]+=v;tag[u]+=v;}
    void push_down(int u)
    {
        if(!tag[u]) return;
        set_tag(u<<1,tag[u]),set_tag(u<<1|1,tag[u]),tag[u]=0;
    }
    void insert(int u,int l,int r,int L,int R,int v)
    {
        if(L<=l && r<=R){set_tag(u,v);return;}
        push_down(u);
        int mid=(l+r)>>1;
        if(L<=mid) insert(u<<1,l,mid,L,R,v);
        if(R>mid) insert(u<<1|1,mid+1,r,L,R,v);
        val[u]=min(val[u<<1],val[u<<1|1]);
    }
    int answer(int u,int l,int r)
    {
        if(l==r) return l;
        push_down(u);
        int mid=(l+r)>>1;
        if(!val[u<<1]) return answer(u<<1,l,mid);
        else return answer(u<<1|1,mid+1,r);
    }
}t;
int nxt[N<<1],to[N<<1],head[N],cnt;
void add(int u,int v)
{
    nxt[++cnt]=head[u];
    to[cnt]=v;
    head[u]=cnt;
}
int dep[N];
bool a_line(int l,int r){return st.get_max(l,r)-st.get_min(l,r)==r-l;}
int t1[N],tt1,t2[N],tt2;
int tn[N],tp;
int mn[N],id[N],lf[N],rf[N],typ[N],tot;
int build(int n)
{
    for(int i=1;i<=n;i++)
    {
        for(;tt1 && num[i]<=num[t1[tt1]];tt1--) t.insert(1,1,n,t1[tt1-1]+1,t1[tt1],num[t1[tt1]]);
        for(;tt2 && num[i]>=num[t2[tt2]];tt2--) t.insert(1,1,n,t2[tt2-1]+1,t2[tt2],-num[t2[tt2]]);
        t.insert(1,1,n,t1[tt1]+1,i,-num[i]);
        t.insert(1,1,n,t2[tt2]+1,i,num[i]);
        t1[++tt1]=t2[++tt2]=i;
        id[i]=++tot;lf[tot]=rf[tot]=i;
        int p=t.answer(1,1,n),u=tot;
        while(tp && lf[tn[tp]]>=p)
        {
            if(typ[tn[tp]] && a_line(mn[tn[tp]],i)){rf[tn[tp]]=i;add(tn[tp],u);u=tn[tp--];continue;}
            if(a_line(lf[tn[tp]],i))
            {
                typ[++tot]=1;
                lf[tot]=lf[tn[tp]],rf[tot]=i;mn[tot]=lf[u];
                add(tot,tn[tp--]),add(tot,u);
            }
            else
            {
                add(++tot,u);
                do add(tot,tn[tp--]); while(tp && !a_line(lf[tn[tp]],i));
                lf[tot]=lf[tn[tp]],rf[tot]=i;
                add(tot,tn[tp--]);
            }
            u=tot;
        }
        tn[++tp]=u;
        t.insert(1,1,n,1,i,-1);
    }
    return tn[1];
}
long long ans;
void dfs(int u,int p)
{
    dep[u]=dep[p]+1;
    int deg=0;
    for(int i=head[u];i;i=nxt[i]) dfs(to[i],u),++deg;
    if(typ[u]) ans+=1ll*deg*(deg-1)/2;
    else ans++;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        num[x]=y;
    }
    st.init(n);
    int rt=build(n);
    dfs(rt,0);
    printf("%lld",ans);
    return 0;
}