LibreOJ 6041 「雅礼集训 2017 Day7」事情的相似度

首先建 SAM，然后问题转化为在 Parent Tree 上编号在 [l,r] 内的点对的 LCA 的深度的最大值。
考虑一个贪心，先在树上做一次启发式合并，维护子树内代表前缀的结点，然后启发式合并时把每个点的前驱后继找出来，与该点形成数对产生贡献。
然后就变成了一个二维数点问题了。
容易发现点对数量规模和启发式合并的复杂度是相同的。

但是我是来写 LCT 的（

考虑从左到右枚举右端点然后维护对应左端点的答案，那么右端点增加一时，要检查其对应结点到根的链上的点维护的最晚出现位置和当前右端点的贡献，然后把它们的最晚出现位置改成当前右端点。
同时在 BIT 上维护后缀最大值即可。

代码：

#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,m,ed[N + 5];
char s[N + 5];
vector< pair<int,int> > qry[N + 5];
int ans[N + 5];
namespace SAM
{
    struct node
    {
        int ch[2];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    inline void insert(int x)
    {
        int p = ++tot,cur = las;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
}
namespace BIT
{
    #define lowbit(x) ((x) & -(x))
    int c[N + 5];
    inline void update(int x,int k)
    {
        for(;x;x -= lowbit(x))
            c[x] = max(c[x],k);
    }
    inline int query(int x)
    {
        int ret = 0;
        for(;x <= n;x += lowbit(x))
            ret = max(ret,c[x]);
        return ret;
    }
}
namespace LCT
{
    struct node
    {
        int fa;
        int las,tag;
        int ch[2];
    } tr[(N << 1) + 5];
    #define chk(p) (tr[tr[p].fa].ch[1] == p)
    #define is_son(p) (tr[tr[p].fa].ch[chk(p)] == p)
    inline void down(int p)
    {
        if(tr[p].tag)
            tr[tr[p].ch[0]].las = tr[tr[p].ch[0]].tag = tr[p].tag,
            tr[tr[p].ch[1]].las = tr[tr[p].ch[1]].tag = tr[p].tag,
            tr[p].tag = 0;
    }
    inline void rotate(int p)
    {
        int x = tr[p].fa,y = tr[x].fa,d = chk(p),t = tr[p].ch[d ^ 1];
        is_son(x) && (tr[y].ch[chk(x)] = p,1),
        tr[p].ch[d ^ 1] = x,tr[x].ch[d] = t,
        t && (tr[t].fa = x),
        tr[x].fa = p,tr[p].fa = y;
    }
    inline void splay(int p)
    {
        static int s[N + 5];
        int top = 0;
        s[++top] = p;
        for(register int x = p;is_son(x);s[++top] = x = tr[x].fa);
        for(;top;down(s[top--]));
        for(register int x;is_son(p);rotate(p))
            x = tr[p].fa,
            is_son(x) && (rotate((chk(p) ^ chk(x)) ? p : x),1);
    }
    inline void access(int p,int pos)
    {
        for(register int cur = p,x = 0;cur;cur = tr[x = cur].fa)
            splay(cur),tr[cur].ch[1] = x,
            tr[cur].las && (BIT::update(tr[cur].las,SAM::sam[cur].len),1);
        splay(p),tr[p].las = tr[p].tag = pos;
    }
    inline void init()
    {
        for(register int i = 1;i <= SAM::tot;++i)
            tr[i].fa = SAM::sam[i].fa;
    }
}
int main()
{
    scanf("%d%d%s",&n,&m,s + 1);
    for(register int i = 1;i <= n;++i)
        SAM::insert(s[i] - '0'),ed[i] = SAM::las;
    LCT::init();
    int l,r;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d",&l,&r),qry[r].push_back(make_pair(l,i));
    for(register int i = 1;i <= n;++i)
    {
        LCT::access(ed[i],i);
        for(register vector< pair<int,int> >::iterator it = qry[i].begin();it != qry[i].end();++it)
            ans[it->second] = BIT::query(it->first);
    }
    for(register int i = 1;i <= m;++i)
        printf("%d\n",ans[i]);
}