[HAOI2017] 供给侧改革 - Trie,离线处理

给定一个随机的 \(01\) 串，设 \(f(l,r)\) 表示在 \(\max_{l\leq p<q \leq r} LCP(s[p\dots n],s[q\dots n])\)，有 \(q\) 个询问，每个询问给定 \([L,R]\)，求 \(\sum_{i=L}^{R-1} f(i,R)\)

Solution

考虑到随机的 \(01\) 串，两个后缀的 LCP 长度不会太长

那么我们要比较两个后缀，只要去比较它的前 \(k\) 个字符，就可以基本确定 LCP

考虑将询问离线，按右端点排序，然后升序扫描

在 Trie 里记录每一个节点被到达的最晚时间，那么我们每次新插入一个后缀 \(i\)，就可以更新计算出对于每一个 \(len\)，使得 \(LCP(j,i) \geq len\) 的最大的 \(j\)，不妨将这个数组记为 \(ans[len]\)

而 \(ans\) 数组一定是单调不严格递减的，于是我们只要扫一遍 \(ans\) 数组即可统计答案

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

struct query {
    int l,r,id;
    bool operator < (const query &b) {
        return r < b.r;
    }
} qu[N];

int n,q,ans[44],res[N];
char s[N];

namespace trie {
    int ch[N*44][2], las[N*44], ind=1;
    void insert(char *s,int l,int r) {
        int p=1;
        for(int i=l;i<=r;i++) {
            int x=s[i]-'0';
            ans[i-l]=max(ans[i-l],las[p]);
            las[p]=l;
            if(!x) {
                if(ch[p][0]==0) ch[p][0]=++ind, las[ind]=-1e9;
                p=ch[p][0];
            }
            else {
                if(ch[p][1]==0) ch[p][1]=++ind, las[ind]=-1e9;
                p=ch[p][1];
            }
        }
        int i=r+1;
        ans[i-l]=max(ans[i-l],las[p]);
        las[p]=l;
    }
}

void solve() {
    ios::sync_with_stdio(false);
    cin>>n>>q;
    cin>>s+1;
    for(int i=1;i<=q;i++) cin>>qu[i].l>>qu[i].r, qu[i].id=i;
    sort(qu+1,qu+q+1);
    int pos=0;
    for(int i=1;i<=q;i++) {
        while(pos<qu[i].r) {
            ++pos;
            trie::insert(s,pos,min(n,pos+40));
        }
        for(int j=1;j<=40;j++)
            res[qu[i].id]+=j*max(0,min(ans[j],pos-1)-max(ans[j+1],qu[i].l-1));
    }
    for(int i=1;i<=q;i++) cout<<res[i]<<endl;
}

signed main() {
    solve();
}

[HAOI2017] 供给侧改革 - Trie,离线处理

原文：https://www.cnblogs.com/mollnn/p/12407913.html