析合树

摘要

作为一个没有去过 WC2019 的人去啃 WC 的课件。别问我为什么这么菜。

翻的时侯翻到一个友好的标题:《简单的连续段数据结构》。打开后,咦!析合树!

另外解释一下本文可能用到的符号: 逻辑与, 逻辑或。

关于段的问题

我们由一个小清新的问题引入:

对于一个 1-n 的排列,我们称一个值域连续的区间为段。问一个排列的段的个数。比如, 的段有:[1,1],[2,2],[3,3],[4,4],[5,5],[2,3],[4,5],[1,3],[2,5],[1,5]。

看到这个东西,感觉要维护区间的值域集合,复杂度好像挺不友好的。线段树可以查询某个区间是否为段,但不太能统计段的个数(也可能是因为我太菜了不会用线段树)

这里我们引入这个神奇的数据结构——析合树!

连续段

在介绍析合树之前,我们先做一些前提条件的限定。鉴于 LCA 的课件的定义十分玄乎,为保证读者的身心健康,我就口糊一些人性化的定义吧。

排列与连续段

排列:定义一个 n 阶排列 P 是一个大小为 n 的序列,使得 取遍 。说得形式化一点,n 阶排列 P 是一个有序集合满足:

  1. .
  2. .
  3. .

连续段:对于排列 P,定义连续段 表示一个区间 ,要求 值域是连续的。说得更形式化一点,对于排列 P,连续段表示一个区间 满足:

特别地,当 时,我们认为这时一个空的连续段,记作

我们称排列 P 的所有连续段的集合为 . 并且我们认为 .

连续段的运算

连续段是依赖区间和值域定义的,于是我们可以定义连续段的交并差的运算。

定义 ,且 。于是连续段的关系和运算可以表示为:

  1. .
  2. .
  3. .
  4. .
  5. .

其实这些运算就是普通的集合交并差放在区间上而已。

连续段的性质

连续段的一些显而易见的性质。我们定义 ,那么有 .

证明?证明的本质就是集合的交并差的运算。

析合树

好的,现在讲到重点了。你可能已经猜到了,析合树正是由连续段组成的一棵树。但是要知道一个排列可能有多达 个连续段,因此我们就要抽出其中更基本的连续段组成析合树。

本原段

其实这个定义全称叫作本原连续段。但笔者认为本原段更为简洁。

对于排列 P,我们认为一个本原段 表示在集合 中,不存在与之相交且不包含的连续段。形式化地定义,我们认为 且满足 .

所有本原段的集合为 . 显而易见, .

显然,本原段之间只有相离或者包含关系。并且你发现一个连续段可以由几个互不相交的本原段构成。最大的本原段就是整个排列本身,它包含了其他所有本原段,因此我们认为本原段可以构成一个树形结构,我们称这个结构为析合树。更严格地说,排列 P 的析合树由排列 P 的所有本原段组成。

前面干讲这么多的定义,不来点图怎么行。考虑排列 . 它的本原段构成的析合树如下:

p1

在图中我们没有标明本原段。而图中每个结点都代表一个本原段。我们只标明了每个本原段的值域。举个例子,结点 代表的本原段就是 。于是这里就有一个问题:什么是析点合点?

析点与合点

这里我们直接给出定义,稍候再来讨论它的正确性。

  1. 值域区间:对于一个结点 u,用 表示该结点的值域区间。
  2. 儿子序列:对于析合树上的一个结点 u,假设它的儿子结点是一个有序序列,该序列是以值域区间为元素的(单个的数 x 可以理解为 的区间)。我们把这个序列称为儿子序列。记作
  3. 儿子排列:对于一个儿子序列 ,把它的元素离散化成正整数后形成的排列称为儿子排列。举个例子,对于结点 ,它的儿子序列为 ,那么把区间排序标个号,则它的儿子排列就为 ;类似的,结点 的儿子排列为 。结点 u 的儿子排列记为 .
  4. 合点:我们认为,儿子排列为顺序或者逆序的点为合点。形式化地说,满足 或者 的点称为合点。叶子结点没有儿子排列,我们也认为它是合点
  5. 析点:不是合点的就是析点。

从图中可以看到,只有 不是合点。因为 的儿子排列是

析点与合点的性质

析点与合点的命名来源于他们的性质。首先我们有一个非常显然的性质:对于析合树中任何的结点 u,其儿子序列区间的并集就是结点 u 的值域区间。即 .

对于一个合点 u:其儿子序列的任意子区间都构成一个连续段。形式化地说,对于 ,有

对于一个析点 u:其儿子序列的任意长度大于 1(这里的长度是指儿子序列中的元素数,不是下标区间的长度)的子区间都构成一个连续段。形式化地说,对于 ,有

合点的性质不难口糊证明。因为合点的儿子排列要么是顺序,要么是倒序,而值域区间也是首位相接,因此只要是连续的一段子序列(区间)都是一个连续段。

对于析点的性质可能很多读者就不太能理解了:为什么任意长度大于 1 的子区间都不构成连续段?

使用反证法。假设对于一个点 u,它的儿子序列中有一个最长的区间 构成了连续段。那么这个 ,也就意味着 是一个本原段!(因为 A 是儿子序列中最长的,因此找不到一个与它相交又不包含的连续段)于是你就没有使用所有的本原段构成这个析合树。矛盾。

析合树的构造

前面讲了这么多零零散散的东西,现在就来具体地讲如何构造析合树。LCA 大佬的线性构造算法我是没看懂的,今天就讲一下比较好懂的 的算法。

增量法

我们考虑增量法。用一个栈维护前 i-1 个元素构成的析合森林。在这里我需要着重强调,析合森林的意思是,在任何时侯,栈中结点要么是析点要么是合点。现在考虑当前结点

  1. 我们先判断它能否成为栈顶结点的儿子,如果能就变成栈顶的儿子,然后把栈顶取出,作为当前结点。重复上述过程直到栈空或者不能成为栈顶结点的儿子。
  2. 如果不能成为栈顶的儿子,就看能不能把栈顶的若干个连续的结点都合并成一个结点(判断能否合并的方法在后面),把合并后的点,作为当前结点。
  3. 重复上述过程直到不能进行为止。然后结束此次增量,直接把当前结点圧栈。

接下来我们仔细解释一下。

具体的策略

我们认为,如果当前点能够成为栈顶结点的儿子,那么栈顶结点是一个合点。如果是析点,那么你合并后这个析点就存在一个子连续段,不满足析点的性质。因此一定是合点。

如果无法成为栈顶结点的儿子,那么我们就看栈顶连续的若干个点能否与当前点一起合并。我们预处理一个数组 表示右端点下标为 的连续段中,左端点的最小值。当前结点为 ,栈顶结点记为

  1. 如果 那么显然当前结点无法合并;
  2. 如果 ,那么这就是两个结点合并,合并后就是一个合点
  3. 如果在栈中存在一个点 的左端点 ,那么一定可以从当前结点合并到 形成一个析点
  4. 否则,我们找到栈中的一个点 使得 。由连续段的差运算可知 也是连续段,于是合并 之后的结点到当前结点成一个析点即可。

判断能否合并

最后,我们考虑如何处理 数组。事实上,一个连续段 等价于区间极差与区间长度 -1 相等。即

而且由于 P 是一个排列,因此对于任意的区间 都有

于是我们就维护 ,那么要找到一个连续段相当于查询一个最小值!

有了上述思路,不难想到这样的算法。对于增量过程中的当前的 i,我们维护一个数组 表示区间 的极差减长度。即

现在我们想知道在 中是否存在一个最小的 使得 。这等价于求 的最小值。求得最小的 j 就是 。如果没有,那么

但是当第 i 次增量结束时,我们需要快速把 数组更新到 i+1 的情况。原本的区间从 变成 ,如果 或者 都会造成 发生变化。如何变化?如果 ,相当于我们把 先减掉 再加上 就完成了 的更新; 同理,相当于 .

那么如果对于一个区间 ,满足 的区间 都相同呢?你已经发现了,那么相当于我们在做一个区间加的操作;同理,当 的区间 都想同时也是一个区间加的操作。同时, 的更新是相互独立的, 因此可以各自更新。

因此我们对 的维护可以这样描述:

  1. 找到最大的 使得 ,那么显然, 这一段数全部小于 ,于是就需要更新 的最大值。由于 是(非严格)单调递增的,因此可以每一段相同的 做相同的更新,即区间加操作。
  2. 更新 同理。
  3. 把每一个 都减 1。因为区间长度加 1。
  4. 查询 :即查询 的最小值的所在的下标

没错,我们可以使用线段树维护 !现在还有一个问题:怎么找到相同的一段使得他们的 都相同?使用单调栈维护!维护两个单调栈分别表示 。那么显然,栈中以相邻两个元素为端点的区间的 是相同的,于是在维护单调栈的时侯顺便更新线段树即可。

具体的维护方法见代码。

讲这么多干巴巴的想必小伙伴也听得云里雾里的,那么我们就先上图吧。长图警告!

p2

实现

最后放一个实现的代码供参考。代码转自 大米饼的博客. 被我加了一些注释

#include<bits/stdc++.h>
#define rg register
using namespace std;
const int N=200010;

int n,m,a[N],st1[N],st2[N],tp1,tp2,rt;
int L[N],R[N],M[N],id[N],cnt,typ[N],bin[20],st[N],tp;

char gc(){
    static char*p1,*p2,s[1000000];
    if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin);
    return(p1==p2)?EOF:*p1++;
}
int rd(){
    int x=0;char c=gc();
    while(c<'0'||c>'9')c=gc();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc();
    return x;
}
char ps[1000000],*pp=ps;
void flush(){fwrite(ps,1,pp-ps,stdout);pp=ps;}
void push(char x){if(pp==ps+1000000)flush();*pp++=x;}
void write(int l,int r){
    static int sta[N],top;
    if(!l)push('0');else{
        while(l)sta[++top]=l%10,l/=10;
        while(top)push(sta[top--]^'0');}
    push(' ');
    if(!r)push('0');else{
        while(r)sta[++top]=r%10,r/=10;
        while(top)push(sta[top--]^'0');}
    push('\n');
}

struct RMQ{// 预处理 RMQ(Max & Min)
    int lg[N],mn[N][17],mx[N][17];
    void chkmn(int&x,int y){if(x>y)x=y;}
    void chkmx(int&x,int y){if(x<y)x=y;}
    void build(){
        for(int i=bin[0]=1;i<20;++i)bin[i]=bin[i-1]<<1;
        for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;++i)mn[i][0]=mx[i][0]=a[i];
        for(int i=1;i<17;++i)
            for(int j=1;j+bin[i]-1<=n;++j)
                mn[j][i]=min(mn[j][i-1],mn[j+bin[i-1]][i-1]),
                    mx[j][i]=max(mx[j][i-1],mx[j+bin[i-1]][i-1]);
    }
    int ask_mn(int l,int r){
        int t=lg[r-l+1];
        return min(mn[l][t],mn[r-bin[t]+1][t]);
    }
    int ask_mx(int l,int r){
        int t=lg[r-l+1];
        return max(mx[l][t],mx[r-bin[t]+1][t]);
    }
}D;
// 维护 L_i

struct SEG{// 线段树
#define ls (k<<1)
#define rs (k<<1|1)
    int mn[N<<1],ly[N<<1];// 区间加;区间最小值
    void pushup(int k){mn[k]=min(mn[ls],mn[rs]);}
    void mfy(int k,int v){mn[k]+=v,ly[k]+=v;}
    void pushdown(int k){if(ly[k])mfy(ls,ly[k]),mfy(rs,ly[k]),ly[k]=0;}
    void update(int k,int l,int r,int x,int y,int v){
        if(l==x&&r==y){mfy(k,v);return;}
        pushdown(k);
        int mid=(l+r)>>1;
        if(y<=mid)update(ls,l,mid,x,y,v);
        else if(x>mid)update(rs,mid+1,r,x,y,v);
        else update(ls,l,mid,x,mid,v),update(rs,mid+1,r,mid+1,y,v);
        pushup(k);
    }
    int query(int k,int l,int r){// 询问 0 的位置
        if(l==r)return l;
        pushdown(k);
        int mid=(l+r)>>1;
        if(!mn[ls])return query(ls,l,mid);
        else return query(rs,mid+1,r);
        // 如果不存在 0 的位置就会自动返回一个极大值
    }
}T;

int o=1,hd[N],dep[N],fa[N][18];
struct Edge{int v,nt;}E[N<<1];
void add(int u,int v){// 树结构加边
    E[o]=(Edge){v,hd[u]};hd[u]=o++;
    //printf("%d %d\n",u,v);
}
void dfs(int u){
    for(int i=1;bin[i]<=dep[u];++i)fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=hd[u];i;i=E[i].nt){
        int v=E[i].v;
        dep[v]=dep[u]+1;
        fa[v][0]=u;
        dfs(v);
    }
}
int go(int u,int d){
    for(int i=0;i<18&&d;++i)if(bin[i]&d)d^=bin[i],u=fa[u][i];
    return u;
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    u=go(u,dep[u]-dep[v]);
    if(u==v)return u;
    for(int i=17;~i;--i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

// 判断当前区间是否为连续段
bool judge(int l,int r){return D.ask_mx(l,r)-D.ask_mn(l,r)==r-l;}

// 建树
void build(){
    for(int i=1;i<=n;++i){
        // 单调栈
        // 在区间 [st1[tp1-1]+1,st1[tp1]] 的最小值就是 a[st1[tp1]]
        // 现在把它出栈,意味着要把多减掉的 Min 加回来。
        // 线段树的叶结点位置 j 维护的是从 j 到当前的 i 的
        //Max{j,i}-Min{j,i}-(i-j)
        // 区间加只是一个 Tag。
        // 维护单调栈的目的是辅助线段树从 i-1 更新到 i。
        // 更新到 i 后,只需要查询全局最小值即可知道是否有解

        while(tp1&&a[i]<=a[st1[tp1]])// 单调递増的栈,维护 Min
            T.update(1,1,n,st1[tp1-1]+1,st1[tp1],a[st1[tp1]]),tp1--;
        while(tp2&&a[i]>=a[st2[tp2]])
            T.update(1,1,n,st2[tp2-1]+1,st2[tp2],-a[st2[tp2]]),tp2--;

        T.update(1,1,n,st1[tp1]+1,i,-a[i]);st1[++tp1]=i;
        T.update(1,1,n,st2[tp2]+1,i,a[i]);st2[++tp2]=i;

        id[i]=++cnt;L[cnt]=R[cnt]=i;// 这里的 L,R 是指值域的上下界
        int le=T.query(1,1,n),now=cnt;
        while(tp&&L[st[tp]]>=le){
            if(typ[st[tp]]&&judge(M[st[tp]],i)){
                // 判断是否能成为儿子,如果能就做
                R[st[tp]]=i, add(st[tp],now), now=st[tp--];
            }else if(judge(L[st[tp]],i)){
                typ[++cnt]=1;// 合点一定是被这样建出来的
                L[cnt]=L[st[tp]], R[cnt]=i, M[cnt]=L[now];
                add(cnt,st[tp--]), add(cnt,now);
                now=cnt;
            }else{
                add(++cnt,now);// 新建一个结点,把 now 添加为儿子
                // 如果从当前结点开始不能构成连续段,就合并。
                // 直到找到一个结点能构成连续段。而且我们一定能找到这样
                // 一个结点。
                do add(cnt,st[tp--]); while(tp&&!judge(L[st[tp]],i));
                L[cnt]=L[st[tp]], R[cnt]=i, add(cnt,st[tp--]);
                now=cnt;
            }
        }
        st[++tp]=now;// 增量结束,把当前点圧栈

        T.update(1,1,n,1,i,-1);// 因为区间右端点向后移动一格,因此整体 -1
    }

    rt=st[1];// 栈中最后剩下的点是根结点
}
void query(int r,int l){
    int x=id[l],y=id[r];
    int z=lca(x,y);
    if(typ[z]&1)
        l=L[go(x,dep[x]-dep[z]-1)],
        r=R[go(y,dep[y]-dep[z]-1)];
    else l=L[z],r=R[z];
    write(l,r);
}// 分 lca 为析或和,这里把叶子看成析的

int main(){
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    n=rd();
    for(int i=1;i<=n;++i)a[i]=rd();
    D.build();
    build();
    dfs(rt);
    m=rd();
    for(int i=1;i<=m;++i)query(rd(),rd());
    return flush(),0;
}
//20190612
// 析合树

  转载请注明: Sshwy's Blog 析合树

 上一篇
Prufer 序列 Prufer 序列
摘要 本文翻译自 e-maxx Prufer Code,兹瓷一下OI-WIKI的计划。另外解释一下,原文的结点是从 0 开始标号的,本文我按照大多数人的习惯改成了从 1 标号。 这篇文章介绍 Prufer 序列 (Prufer code)
2019.07.07
下一篇 
线段树与历史区间最值问题 线段树与历史区间最值问题
摘要 读 jry《区间最值操作与历史最值问题》 前言仍然是线段树的应用问题。在前文中我们探讨了线段树的基及其应用。如果对这方面了解较少的同学请移步《线段树初步》、《线段树应用》。本文将继续讲解线段树在区间最值与历史最值问题上的应用。 区间
2019.06.19
  目录