#6041. 「雅礼集训 2017 Day7」事情的相似度 [set启发式合并+树状数组扫描线]

SAM 两个前缀的最长后缀等价于两个点的 \(len_{lca}\) , 题目转化为求 \(l \leq x , y \leq r\) , \(max\{len_{lca(x,y)}\}\)
// powered by c++11

// by Isaunoya

#include <bits/stdc++.h>

#define rep(i, x, y) for (register int i = (x); i <= (y); ++i)

#define Rep(i, x, y) for (register int i = (x); i >= (y); --i)

using namespace std;

using db = double;

using ll = long long;

using uint = unsigned int;

#define Tp template

using pii = pair<int, int>;

#define fir first

#define sec second

Tp<class T> void cmax(T& x, const T& y) {

    if (x < y)

        x = y;

}

Tp<class T> void cmin(T& x, const T& y) {

    if (x > y)

        x = y;

}

#define all(v) v.begin(), v.end()

#define sz(v) ((int)v.size())

#define pb emplace_back

Tp<class T> void sort(vector<T>& v) { sort(all(v)); }

Tp<class T> void reverse(vector<T>& v) { reverse(all(v)); }

Tp<class T> void unique(vector<T>& v) { sort(all(v)), v.erase(unique(all(v)), v.end()); }

const int SZ = 1 << 23 | 233;

struct FILEIN {

    char qwq[SZ], *S = qwq, *T = qwq, ch;

#ifdef __WIN64

#define GETC getchar

#else

    char GETC() { return (S == T) && (T = (S = qwq) + fread(qwq, 1, SZ, stdin), S == T) ? EOF : *S++; }

#endif

    FILEIN& operator>>(char& c) {

        while (isspace(c = GETC()))

            ;

        return *this;

    }

    FILEIN& operator>>(string& s) {

        while (isspace(ch = GETC()))

            ;

        s = ch;

        while (!isspace(ch = GETC())) s += ch;

        return *this;

    }

    Tp<class T> void read(T& x) {

        bool sign = 0;

        while ((ch = GETC()) < 48) sign ^= (ch == 45);

        x = (ch ^ 48);

        while ((ch = GETC()) > 47) x = (x << 1) + (x << 3) + (ch ^ 48);

        x = sign ? -x : x;

    }

    FILEIN& operator>>(int& x) { return read(x), *this; }

    FILEIN& operator>>(ll& x) { return read(x), *this; }

} in;

struct FILEOUT {

    const static int LIMIT = 1 << 22;

    char quq[SZ], ST[233];

    int sz, O;

    ~FILEOUT() { flush(); }

    void flush() {

        fwrite(quq, 1, O, stdout);

        fflush(stdout);

        O = 0;

    }

    FILEOUT& operator<<(char c) { return quq[O++] = c, *this; }

    FILEOUT& operator<<(string str) {

        if (O > LIMIT)

            flush();

        for (char c : str) quq[O++] = c;

        return *this;

    }

    Tp<class T> void write(T x) {

        if (O > LIMIT)

            flush();

        if (x < 0) {

            quq[O++] = 45;

            x = -x;

        }

        do {

            ST[++sz] = x % 10 ^ 48;

            x /= 10;

        } while (x);

        while (sz) quq[O++] = ST[sz--];

    }

    FILEOUT& operator<<(int x) { return write(x), *this; }

    FILEOUT& operator<<(ll x) { return write(x), *this; }

} out;

// #define int long long

int n, m;

const int maxn = 2e5 + 52;

vector<int> g[maxn];

void add(int u, int v) { g[u].pb(v); }

struct BIT {

    int c[maxn];

    int low(int x) { return x & -x; }

    void add(int x, int y) {

        for (; x; x ^= low(x)) cmax(c[x], y);

    }

    int qry(int x) {

        int ans = 0;

        for (; x <= n; x += low(x)) cmax(ans, c[x]);

        return ans;

    }

} bit;

vector<pii> chg[maxn];

struct SAM {

    int cnt = 1, last = 1, ch[maxn][2], fa[maxn], len[maxn], t[maxn], rt[maxn];

    void ins(int c, int pos) {

        int p = last, np = last = ++cnt;

        len[np] = len[p] + 1;

        t[pos] = np;

        for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;

        if (!p)

            fa[np] = 1;

        else {

            int q = ch[p][c];

            if (len[q] == len[p] + 1)

                fa[np] = q;

            else {

                int nq = ++cnt;

                len[nq] = len[p] + 1;

                ch[nq][0] = ch[q][0], ch[nq][1] = ch[q][1];

                fa[nq] = fa[q], fa[q] = fa[np] = nq;

                for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;

            }

        }

    }

    set<int> s[maxn];

    void merge(int a, int b, int len) {

        for (auto it = s[b].begin(); it != s[b].end(); ++it) {

            s[a].insert(*it);

            auto pre = s[a].find(*it), nxt = pre;

            ++nxt;

            if (pre != s[a].begin())

                pre--, chg[*it].pb(*pre, len);

            if (nxt != s[a].end())

                chg[*nxt].pb(*it, len);

            s[a].erase(*it);

        }

        for (int x : s[b]) s[a].insert(x);

    }

    void dfs(int u) {

        for (int v : g[u]) {

            dfs(v);  // if(! len[u]) continue ;

            if (s[rt[u]].size() > s[rt[v]].size())

                merge(rt[u], rt[v], len[u]);

            else

                merge(rt[v], rt[u], len[u]), rt[u] = rt[v];

        }

    }

    void build() {

        for (int i = 1; i <= n; i++) s[t[i]].insert(i);

        for (int i = 2; i <= cnt; i++) add(fa[i], i);

        for (int i = 2; i <= cnt; i++) rt[i] = i;

        dfs(1);

    }

} sam;

vector<pii> qr[maxn];

int ans[maxn];

signed main() {

    // code begin.

    in >> n >> m;

    string s;

    in >> s;

    int pos = 0;

    for (char c : s) sam.ins(c ^ '0', ++pos);

    sam.build();

    rep(i, 1, m) {

        int l, r;

        in >> l >> r;

        qr[r].pb(l, i);

    }

    rep(i, 1, n) {

        for (auto x : chg[i]) bit.add(x.first, x.second);

        for (auto x : qr[i]) ans[x.second] = bit.qry(x.first);

    }

    rep(i, 1, m) out << ans[i] << '\n';

    return 0;

    // code end.

}
巴特西

#6041. 「雅礼集训 2017 Day7」事情的相似度 [set启发式合并+树状数组扫描线]

最新文章

热门文章
