526互联

UVA13023 Text Processor

发布时间 2024-01-10 08:08:35作者: zltzlt

洛谷传送门

区间本质不同子串个数。

考虑类比区间数颜色。扫描线扫询问的 \(r = i\)，然后对于一个 \(i\) 的后缀 \(S[j : i]\)，我们把它上一次出现时的左端点位置 \(-1\)，现在的左端点位置（即 \(j\)）\(+1\)。那么查询就是 \([l, r]\) 的区间和。

考虑把 SAM 建出来。设 \(S[1 : i]\) 对应的点为 \(a_i\)。那么相当于我们对于每个点维护一个颜色 \(b_u\) 表示这个等价类上一次出现的右端点，每次把 parent tree 上 \(a_i\) 到根的点拎出来做一次操作。设点 \(u\) 的长度区间为 \([l_u, r_u]\)，那么一次操作相当于把 \([b_u - r_u + 1, b_u - l_u + 1]\) 的位置 \(-1\)。最后把 \([1, i]\) \(+1\)。

剩下的部分是 P9340 [JOISC 2023 Day3] Tourism。考虑树剖后把树拍到 dfs 序上，每次推平 \(O(\log n)\) 个区间。

但是事实上因为我们每次只是对一条重链前缀赋值，所以不用真的去实现一个 ODT。每条重链分别维护一些从浅到深的连续段即可。

总时间复杂度为 \(O(n \log^2 n + m \log n)\)。

code 
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 200100;

ll n, m, ans[maxn], a[maxn], b[maxn], K;
vector<pii> qq[maxn];
vector<int> G[maxn];
char s[maxn];

struct SAM {
    int lst, tot, fa[maxn], ch[maxn][26], len[maxn];
    
    inline void init() {
        for (int i = 1; i <= tot; ++i) {
            fa[i] = len[i] = 0;
            mems(ch[i], 0);
        }
        lst = tot = 1;
    }
    
    inline void insert(int c) {
        int u = ++tot, p = lst;
        len[u] = len[p] + 1;
        lst = u;
        for (; p && !ch[p][c]; p = fa[p]) {
            ch[p][c] = u;
        }
        if (!p) {
            fa[u] = 1;
            return;
        }
        int q = ch[p][c];
        if (len[q] == len[p] + 1) {
            fa[u] = q;
            return;
        }
        int nq = ++tot;
        fa[nq] = fa[q];
        len[nq] = len[p] + 1;
        memcpy(ch[nq], ch[q], sizeof(ch[nq]));
        fa[u] = fa[q] = nq;
        for (; p && ch[p][c] == q; p = fa[p]) {
            ch[p][c] = nq;
        }
    }
} sam;

namespace BIT {
    ll a[maxn], b[maxn];
    
    inline void init() {
    	for (int i = 1; i <= n; ++i) {
    		a[i] = b[i] = 0;
    	}
    }
    
    inline void update(ll x, ll d) {
        for (int i = x; i <= n; i += (i & (-i))) {
            a[i] += d;
            b[i] += x * d;
        }
    }
    
    inline void update(ll l, ll r, ll x) {
        update(l, x);
        update(r + 1, -x);
    }
    
    inline ll query(ll x) {
        ll res = 0;
        for (int i = x; i; i -= (i & (-i))) {
            res += a[i] * (x + 1) - b[i];
        }
        return res;
    }
    
    inline ll query(ll l, ll r) {
        return query(r) - query(l - 1);
    }
}

int fa[maxn], sz[maxn], dep[maxn], son[maxn], top[maxn], dfn[maxn], rnk[maxn], tim;

int dfs(int u, int f, int d) {
    fa[u] = f;
    sz[u] = 1;
    dep[u] = d;
    int mx = -1;
    for (int v : G[u]) {
        if (v == f) {
            continue;
        }
        sz[u] += dfs(v, u, d + 1);
        if (sz[v] > mx) {
            son[u] = v;
            mx = sz[v];
        }
    }
    return sz[u];
}

void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++tim;
    rnk[tim] = u;
    if (!son[u]) {
        return;
    }
    dfs2(son[u], tp);
    for (int v : G[u]) {
        if (!dfn[v]) {
            dfs2(v, v);
        }
    }
}

struct node {
    int l, r, x;
    node(int a = 0, int b = 0, int c = 0) : l(a), r(b), x(c) {}
};
vector<node> vc[maxn];

inline void update(int u, int x) {
    BIT::update(1, x, 1);
    while (u) {
        while (vc[top[u]].size()) {
            node p = vc[top[u]].back();
            vc[top[u]].pop_back();
            if (p.r <= dfn[u]) {
                int l = sam.len[fa[rnk[p.l]]] + 1, r = sam.len[rnk[p.r]];
                BIT::update(p.x - r + 1, p.x - l + 1, -1);
                if (p.r == dfn[u]) {
                    break;
                }
            } else {
                int l = sam.len[fa[rnk[p.l]]] + 1, r = sam.len[u];
                BIT::update(p.x - r + 1, p.x - l + 1, -1);
                vc[top[u]].pb(dfn[u] + 1, p.r, p.x);
                break;
            }
        }
        vc[top[u]].pb(dfn[top[u]], dfn[u], x);
        u = fa[top[u]];
    }
}

void solve() {
	tim = 0;
    n = strlen(s + 1);
    sam.init();
    for (int i = 1; i <= n; ++i) {
        sam.insert(s[i] - 'a');
        a[i] = sam.lst;
    }
    for (int i = 1, l; i <= m; ++i) {
        scanf("%d", &l);
        qq[l + K - 1].pb(l, i);
    }
    for (int i = 2; i <= sam.tot; ++i) {
        G[sam.fa[i]].pb(i);
    }
    dfs(1, 0, 1);
    dfs2(1, 1);
    BIT::init();
    for (int i = 1; i <= n; ++i) {
        update(a[i], i);
        for (pii p : qq[i]) {
            ans[p.scd] = BIT::query(p.fst, i);
        }
        vector<pii>().swap(qq[i]);
    }
    for (int i = 1; i <= m; ++i) {
        printf("%lld\n", ans[i]);
    }
    for (int i = 1; i <= sam.tot; ++i) {
    	fa[i] = sz[i] = son[i] = dep[i] = dfn[i] = top[i] = 0;
    	vector<int>().swap(G[i]);
    	vector<node>().swap(vc[i]);
    }
}

int main() {
    while (scanf("%s%lld%lld", s + 1, &m, &K) == 3) {
        solve();
    }
    return 0;
}