如何用猫树水掉 st 表模板题

· · 题解

众所周知，无良 cz 今天加强了 st 表板题的数据，卡掉了线段树，树状数组等查询带 log 的数据结构。

但是 st 表的板题显然是不能用 st 表做的呀！所以我们需要另一个查询是线性的数据结构。

这里，我们使用猫树。

猫树是一种支持 O(n\log n)+O(1)+O(n\log n) 查询区间半群信息的数据结构，OI 界首先见于 immortalCO（猫老师）的博客，故名猫树。

首先声明这只是为了写题解而写的一个教程，并不是专门的学习笔记，所以有些地方可能讲得并不够详细。如果真的要学习猫树，建议去洛谷日报或者猫老师的原始博客。

这东西的思想大概是这样的：建一个类似于线段树一样的东西，然后在每个节点维护中点左边的所有点到中点的答案以及中点到中点右边所有点的答案。查询的时候找到某一个节点使得左右端点都在这个区间中并且位于中点两侧，然后合并答案。

如果直接从上往下去找的话复杂度带一个 log，我们考虑优化掉这个 log。

其实我们可以发现这个区间就是左右端点所对应节点的 lca，怎么去求一下 lca 就行了。

但是有更简单的做法。我们把数组的长度补到二的幂（在后面加零），我们发现两个节点的 lca 就是他们二进制表示的 lcp。

然后如果两个数异或之后，你会发现它们的 lcp 的部分都变成零了，也就是最高位往后挪了 lcp 这么多。

这样我们预处理一下所有数的最高位就行了。

实现上，我们可以把每一层的所有节点的信息存在一个数组里，然后只需要知道 lca 的深度即可。

另外每个数组开几倍要好好注意一下，我 RE 了一面才过……

下面是我自己觉得比较好看的实现：

#include<algorithm>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=1e5+5;
int n,m,a[maxn*2];
int f[maxn*2][25],pos[maxn*2];
void build(int o,int l,int r,int d){
    if(l==r){
        pos[r]=o;
        return;
    }
    int mid=l+(r-l)/2;
    build(o*2,l,mid,d+1);
    build(o*2+1,mid+1,r,d+1);
    f[mid][d]=a[mid];
    for(int i=mid-1;i>=l;i--)
        f[i][d]=max(f[i+1][d],a[i]);
    f[mid+1][d]=a[mid+1];
    for(int i=mid+2;i<=r;i++)
        f[i][d]=max(f[i-1][d],a[i]);
}
int lg[maxn*4];
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    m=readint();
    for(int i=1;i<=n;i++) a[i]=readint();
    int len=1;
    while(len<n) len*=2;
    build(1,1,len,1);
    lg[0]=lg[1]=0;
    for(int i=2;i<=len*2;i++) lg[i]=lg[i/2]+1;
    while(m--){
        int l,r;
        l=readint();
        r=readint();
        if(l==r){
            printf("%d\n",a[r]);
            continue;
        }
        int k=lg[pos[r]]-lg[pos[l]^pos[r]];
        printf("%d\n",max(f[l][k],f[r][k]));
    }
    return 0;
}

据说猫树的本质是把分治的过程离线下来。（所以其实可以直接离线询问然后分治可以做到线性空间）

另外还有一种科技是利用分块思想，每层分根号个块，可以做到 O(n\log\log n)+O(1)+O(n\log\log n)，这种科技叫做 sqrt tree，跟猫树有类似之处，我有时间再补吧。

lxl 还给过我一种科技，但是……截图我弄丢了（捂脸）。大概就是也是按照类似 sqrt tree 的方法分块，然后每层块长记得是 \log，\log^{*}，\log^{**} 这样子（似乎？），分 \alpha(n) 层，就可以做到 O(n\alpha(n))+O(1)+O(n\alpha(n)) 这样子，是很厉害的科技了。

总之……就这样吧，我们就用猫树水掉了 st 表的模板题（大雾）。