题解 P3865 【【模板】ST表】

· · 题解

magic!$ $O(n)$在线$RMQ

前置知识:笛卡尔树

以下标作为节点建立的二叉搜索树，同时权值满足堆的性质.这题取max就是大根堆.

对就是一个Treap

对一个序列建立笛卡尔树

使用单调栈维护最右边一条链上的点，容易知道这条链是从上到下递减的，每次在最右边加入一个元素w[i]，如果它比栈顶大就弹栈，这样就可以找到它应该插入的位置.记录最后一次弹栈的元素last，令栈顶的右儿子是w[i],w[i]的左儿子是last即可.容易知道是O(n)的.

建树代码

void build_tree()
{
    int top=1;stack[1]=1;//为了方便，单调栈只记录下标
    for(int i=2;i<=n;i++)
    {
        int lst=0;
        while(top&&w[i]>w[stack[top]])lst=stack[top--];//弹栈
        fa[lst]=i;if(top)fa[i]=stack[top];
        stack[++top]=i;
    }
    for(int i=1;i<=n;i++)if(fa[i])ade(fa[i],i);else S=i;
    //S是根
}

容易知道一段区间[l,r]的max即笛卡尔树上l和r的LCA

然后如果你去翻了翻顶上kcz\ rank1的代码，你发现他做到这里就结束了，底下是一个暴力查询.

我们知道这样建出来的树是不平衡的，所以只需要构造一个单调递减的数列，然后每次都查单点就可以卡到O(n^2)，但是数据随机...随机...

不管了还是回到解题上来.

这题没强制在线所以可以Tarjan求LCA，O(n+m).

强制在线?

考虑怎么在O(n+m)的时间内在线求一个LCA

转成RMQ去做(所以绕了一大圈又转回来了)，考虑树的欧拉序遍历.

欧拉序就是第一次遍历的时候记录一下dfs序，每次访问完一个儿子之后再记录一个dfs序.

下面是一张灵魂图示

它的欧拉序是1\ 2\ 4\ 2\ 5\ 2\ 1\ 3\ 1

长度是多少呢?我们知道除了整棵树都要遍历一遍之外，每个点都有它的儿子个数son[i]遍重复

所以len=n+\sum son[i]=2n-1

记点i的深度是dep[i]，在欧拉序中第一次出现的位置是first[i]；欧拉序的第i个位置所对应的点是point[i].

我们发现一个性质就是两个点l,r的lca是min\{dep[point[i]]|first[l]\leq i\leq first[r]\}所对应的点，也就是两点欧拉序之间深度最低的那个点.这个性质非常容易证明，因为两个点欧拉序第一次出现的位置之间不会有比lca深度更小的点且lca一定会出现.(其实不是第一次也一样233)

于是我们把lca转化成了rmq.

如果只是算rmq没什么用，但是我们注意到这个rmq有一个非常好的性质，即相邻两个元素之间的差只会是1或-1

这意味着什么呢?如果我们把长为n的序列分块，块的大小是b的话，只有min(2^b,n)个本质不同的块，因为差分之后每个元素只有两种取值(第一个元素取哪个都行).

为了O(1)查询区间的rmq，我们需要预处理块和块之间的rmq和每个块内的rmq.使用ST表来处理块间rmq，复杂度O(\frac{n}{b}\log\frac{n}{b})=O(\frac{n}{b}\log n)；预处理2^b种本质不同的情况，复杂度O(min(2^b,n)b\log b).需要在两者中间取一个平衡.令b=\left\lfloor\frac{\log n}{2}\right\rfloor，那么前一个式子化成O(n)，后一个式子化成O(\sqrt{n}\ b\log b)因为b=O(\log n)渐进小于任何多项式函数，所以后面这个东西是小于O(n)的，从而整体复杂度O(n).

可以预测到代码复杂度极高，所以没什么用.不过空间同样是O(n)的，也比ST表更加优越就是常数不知大到哪里去

其实也没有多长，就130行，和一个较复杂线段树差不多.压一压行更短.

代码丑的一匹qwq

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=1e9;
int n,m,w[2000000],lg2[1500000];
int pos[1500000],lst[1500000],dep[1500000],id,mm,S,ch[1500000][2],stack[1500000];
struct LIM_RMQ
{
    int w[1500000],bl[1500000],blo,L[150000],R[150000],pos[10000],val[150000],minn[150000],minpos[150000],t[1000],n_st;
    struct ST_node{int f,id;bool operator <(const ST_node &tmp)const{return f<tmp.f;}};
    struct STable
    {
        ST_node a[4][12];//n=1e6的话logn/2只有9...所以放心开
        void make(int w[],int n)
        {
            for(int i=1;i<=n;i++)a[0][i]=(ST_node){w[i],i};
            for(int i=1;(1<<i)<=n;i++)//st表，不过要同时处理出最小值所在的位置
                for(int j=1;j+(1<<i)-1<=n;j++)
                    a[i][j]=min(a[i-1][j],a[i-1][j+(1<<(i-1))]);
        }
        ST_node query(int l,int r)
        {
            int len=lg2[r-l+1];
            return min(a[len][l],a[len][r-(1<<len)+1]);
        }
    }st[10000];//这里只有sqrt(n)个，也不用开这么大
    struct STable_block
    {
        ST_node a[20][150000];//这个占空间最大了吧...不过也只是O(n)的
        void make(int w[],int n)
        {
            for(int i=1;i<=n;i++)a[0][i]=(ST_node){w[i],i};
            for(int i=1;(1<<i)<=n;i++)
                for(int j=1;j+(1<<i)-1<=n;j++)
                    a[i][j]=min(a[i-1][j],a[i-1][j+(1<<(i-1))]);
        }
        ST_node query(int l,int r)
        {
            int len=lg2[r-l+1];//细节，math库的log2函数不能看做O(1)的，要提前处理
            return min(a[len][l],a[len][r-(1<<len)+1]);
        }
    }st_block;
    void make(int a[],int n)
    {
        for(int i=1;i<=n;i++)w[i]=a[i];
        lg2[1]=0;for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;//处理log2
        blo=max(lg2[n]>>1,1);//分块
        for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1;
        for(int i=1;i<=bl[n];i++)L[i]=(i-1)*blo+1,R[i]=min(i*blo,n),minn[i]=inf;
        w[0]=w[1]-1;
        for(int i=1;i<=bl[n];i++)
        {
            int tmp=0,nn=0;
            for(int j=L[i];j<=R[i];j++)
            {
                t[++nn]=w[j],tmp=tmp<<1|(w[j]-w[j-1]==1?1:0);
                if(w[j]<minn[i])minn[i]=w[j],minpos[i]=j;
                //可以用一个状压来表示本质
            }
            if(!pos[tmp])st[pos[tmp]=++n_st].make(t,nn);
            val[i]=pos[tmp];//记下每个块属于哪一个本质
        }
        st_block.make(minn,bl[n]);//块间rmq
    }
    ST_node query_block(int id,int l,int r){ST_node t=st[val[id]].query(l-L[id]+1,r-L[id]+1);return (ST_node){t.f,t.id+L[id]-1};}
    //实际位置=块左端点+块内查询位置-1，如果你把块内查询从0开始写就可以省略-1
    int query(int l,int r)
    {
        int bll=bl[l],blr=bl[r];
        if(bll==blr)return query_block(bll,l,r).id;//一个块
        int ml=query_block(bll,l,R[bll]).id,mr=query_block(blr,L[blr],r).id,mm;
        if(w[ml]<w[mr])mm=ml;else mm=mr;//两端零散块
        if(bll+1<=blr-1)//整块
        {
            int mmid=minpos[st_block.query(bll+1,blr-1).id];
            if(w[mmid]<w[mm])mm=mmid;
        }
        return mm;
    }
}a;
void dfs(int u,int depth)
{
    lst[u]=++id,pos[id]=u;dep[id]=depth;//处理欧拉序列
    for(int i=0;i<=1;i++)
        if(ch[u][i])
        {
            dfs(ch[u][i],depth+1);
            pos[++id]=u,dep[id]=depth;
        }
}
int getin()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
int wt[30];
void putout(int x)
{
    if(!x){putchar('0');return;}
    int l=0;
    while(x)wt[++l]=x%10,x/=10;
    while(l)putchar(wt[l--]+48);
    puts("");
}
void build_tree()//笛卡尔树
{
    int top=1;stack[1]=S=1;//开始根为1
    for(int i=2;i<=n;i++)
    {
        int lst=0;
        while(top&&w[i]>w[stack[top]])lst=stack[top--];
        if(lst)ch[i][0]=lst;
        if(top)ch[stack[top]][1]=i;else S=i;
        stack[++top]=i;
    }
    dfs(S,1);
}
int main()
{
    n=getin(),m=getin();
    for(int i=1;i<=n;i++)w[i]=getin();
    build_tree();
    a.make(dep,id);
    for(int i=1;i<=m;i++)
    {
        int l=lst[getin()],r=lst[getin()];
        if(l>r)swap(l,r);//可能第一次出现的位置是反过来的
        putout(w[pos[a.query(l,r)]]);
    }
}

其实也没那么长，因为有两个ST表是重复的可以复制粘贴.主要的代码长度就在分块和ST表上.

最多用来写写LCA吧233 纯lca只有100行，比树剖长不了多少