Problem C: 重复子串(string)

/*
一个性质？ right集合中只有相邻的位置才会有用
那么考虑set启发式合并， 能够求出大概nlogn个有用的对
那么将这些对按照右端点排序， 查询也按照右端点排序就可以离线维护信息
然后需要维护答案的话？？ 区间和一次函数取max？？？
应该有别的办法吧
普通线段树就好了 
*/

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
#include<iostream>
#define ll long long
#define mmp make_pair
#define M 200010
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
set<int> st[M];
set<int>::iterator it, tt;
int ch[M][26], fa[M], len[M], sz[M], ans[M], lst = 1, cnt = 1, n, m, tp;
char s[M];
vector<int> to[M];
struct Note {
    int l, r, max;
    bool operator < (const Note &b) const {
        return this->r <     b.r;
    }
} note[M * 60], que[M];

void insert(int pl, int c) {
    int p = ++cnt, f = lst;
    lst = p;
    len[p] = len[f] + 1;
    while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];
    if(f == 0) fa[p] = 1;
    else {
        int q = ch[f][c];
        if(len[q] == len[f] + 1) fa[p] = q;
        else {
            int nq = ++cnt;
            len[nq] = len[f] + 1;
            fa[nq] = fa[q];
            memcpy(ch[nq], ch[q], sizeof(ch[q]));
            fa[p] = fa[q] = nq;
            while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];
        }
    }
    sz[p] = 1;
    st[p].insert(pl);
}
int id[M];

bool cmp(int a, int b) {
    return sz[a] > sz[b];
}

void dfs(int now) {
    id[now] = now;
    int flag = sz[now];
    for(int i = 0; i < to[now].size(); i++) {
        int vj = to[now][i];
        dfs(vj);
        sz[now] += sz[vj];
    }
    if(now == 1) return;
    sort(to[now].begin(), to[now].end(), cmp);
    if(to[now].size() != 0) {
        id[now] = id[to[now][0]];
        if(flag) {
            int v = *st[now].begin();
            it = st[id[now]].lower_bound(v);
            if(it != st[id[now]].end()) {
                note[++tp] = (Note) {
                    v, *it, len[now]
                };
            }
            if(it != st[id[now]].begin()) {
                it--;
                note[++tp] = (Note) {
                    *it, v, len[now]
                };
            }
            st[id[now]].insert(v);
        }
        for(int i = 1; i < to[now].size(); i++) {
            int vj = to[now][i];
            it = st[id[vj]].begin();
            while(it != st[id[vj]].end()) {
                int v = *it++;
                tt = st[id[now]].lower_bound(v);
                if(tt != st[id[now]].end()) {
                    note[++tp] = (Note) {
                        v, *tt, len[now]
                    };
                }
                if(tt != st[id[now]].begin()) {
                    tt--;
                    note[++tp] = (Note) {
                        *tt, v, len[now]
                    };
                }
                st[id[now]].insert(v);
            }
        }
    }
}


struct Black_ {
#define ls now << 1
#define rs now << 1 | 1
#define lson l, mid, now << 1
#define rson mid + 1, r, now << 1 | 1
    int t[M << 2], len[M << 2], ver[M << 2], maxx[M << 2];

    void build(int l, int r, int now) {
        len[now] = r - l + 1;
        ver[now] = -0x3e3e3e3e;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lson), build(rson);
    }

    void add(int now, int v) {
        ver[now] = max(ver[now], v);
        maxx[now] = max(maxx[now], ver[now] + len[now]);
    }
    void pushup(int now) {
        maxx[now] = max(maxx[now], max(maxx[ls], maxx[rs]));
    }
    void pushdown(int now) {
        add(rs, ver[now]);
        add(ls, ver[now] + len[rs]);
    }

    int que(int l, int r, int now, int ln, int rn) {
        if(l > rn || r < ln) return 0;
        if(l >= ln && r <= rn) return maxx[now];
        int mid = (l + r) >> 1;
        pushdown(now);
        return max(que(lson, ln, rn), que(rson, ln, rn));
    }
    void modi(int l, int r, int now, int ln, int rn, int v) {
        if(l > rn || r < ln) return;
        if(l >= ln && r <= rn) {
            add(now, v);
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(now);
        modi(lson, ln, rn, v + min(max(rn - mid, 0), len[rs]));
        modi(rson, ln, rn, v);
        pushup(now);
    }
    void modify(int r, int v) {
        modi(1, n, 1, r - v + 1, r, 0);
    }
    int query(int l, int r) {
        return que(1, n, 1, l, r);
    }
} Seg;

int main() {
//  freopen("string_example_3.in", "r", stdin); freopen("zz.out", "w", stdout);
    n = read(), m = read();
    scanf("%s", s + 1);
    for(int i = 1; i <= n; i++) insert(i, s[i] - 'a');
    for(int i = 2; i <= cnt; i++) to[fa[i]].push_back(i);
    dfs(1);
    for(int i = 1; i <= m; i++) que[i].l = read(), que[i].r = read(), que[i].max = i;
    sort(note + 1, note + tp + 1);
//  puts(s + 1);
//  for(int i = 1; i <= tp; i++) {
//      cerr<< note[i].l << " " << note[i].r << " " << note[i].max << "\n";
//  }
//  cerr << tp << "\n";
    sort(que + 1, que + m + 1);
    int tp1 = 1, tp2 = 1;
    Seg.build(1, n, 1);
    for(int i = 1; i <= n; i++) {
        while(tp1 <= tp && note[tp1].r <= i) {
            Seg.modify(note[tp1].l, note[tp1].max);
            tp1++;
        }
        while(tp2 <= m && que[tp2].r <= i) {
            ans[que[tp2].max] = Seg.query(que[tp2].l, que[tp2].r);
            tp2++;
        }
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << "\n";
    return 0;
}

Problem C: 重复子串(string)

原文：https://www.cnblogs.com/luoyibujue/p/10719528.html