题解：P4143 采集矿石

· · 题解

我们考察钦定一个左端点，右端点越往右，排名单调减少，\sum a 单调上升。所以 \operatorname{rk}-\sum a 是具有可二分性的，同时每个左端点最多对应一个右端点。

考虑枚举左端点二分出结果，此时只需要维护每个右端点的 \operatorname{rk}。以后缀排序后的顺序扫，则每次前 \operatorname{height}_i 个的排名不变。因为后缀被排序了，第 \operatorname{height}_i+1 个就是上一行的最后一个之后的排名，后面的排名是连续的。

可以做到 1\log，2\log 能过。

#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define int long long
int L[N << 2], R[N << 2], tag[N << 2], val[N << 2];

inline void cov(int u, int x) {
    if (~x)
        val[u] = (R[u] - L[u] + 1) * x, tag[u] = x;
}

inline void down(int u) {
    if (~tag[u])
        cov(u * 2, tag[u]), cov(u * 2 + 1, tag[u]), tag[u] = -1;
}

inline void up(int u) {
    val[u] = val[u * 2] + val[u * 2 + 1];
}

void build(int l, int r, int p) {
    L[p] = l, R[p] = r, tag[p] = -1;
    if (l == r)
        return;
    int m = (l + r) / 2;
    build(l, m, p * 2), build(m + 1, r, p * 2 + 1), up(p);
}

int qus(int l, int r, int p) {
    if (l <= L[p] && r >= R[p])
        return val[p];
    if (l > R[p] || r < L[p])
        return 0;
    down(p);
    return qus(l, r, p * 2) + qus(l, r, p * 2 + 1);
}

void add(int l, int r, int p, int v) {
    if (l <= L[p] && r >= R[p])
        return cov(p, v);
    if (l > R[p] || r < L[p])
        return;
    down(p), add(l, r, p * 2, v), add(l, r, p * 2 + 1, v), up(p);
}

inline int que(int r) {
    return qus(1, r, 1);
}
int ans[N], sa[N], rk[N << 1], hei[N], cnt[N], oldsa[N << 1], oldrk[N << 1], a[N], n, tot, res;
string s;

void SA() {
    for (int i = 1; i <= n; i++)
        cnt[rk[i] = s[i] - 'a' + 1]++;
    for (int i = 1; i <= 26; i++)
        cnt[i] += cnt[i - 1];
    for (int i = n; i; i--)
        sa[cnt[rk[i]]--] = i;
    for (int i = 1; i <= n; i++)
        oldrk[i] = rk[i];
    for (int i = 1, p = 0; i <= n; i++)
        rk[sa[i]] = (p += (oldrk[sa[i - 1]] != oldrk[sa[i]]));
    for (int d = 1; d < n; d <<= 1) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)
            cnt[rk[sa[i] + d]]++;
        for (int i = 1; i <= n; i++)
            cnt[i] += cnt[i - 1];
        for (int i = 1; i <= n; i++)
            oldsa[i] = sa[i];
        for (int i = n; i; i--)
            sa[cnt[rk[oldsa[i] + d]]--] = oldsa[i];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; i++)
            cnt[rk[sa[i]]]++;
        for (int i = 1; i <= n; i++)
            cnt[i] += cnt[i - 1];
        for (int i = 1; i <= n; i++)
            oldsa[i] = sa[i];
        for (int i = n; i; i--)
            sa[cnt[rk[oldsa[i]]]--] = oldsa[i];
        for (int i = 1; i <= n; i++)
            oldrk[i] = rk[i];
        for (int i = 1, p = 0; i <= n; i++)
            rk[sa[i]] = (p += (oldrk[sa[i - 1]] != oldrk[sa[i]] || oldrk[sa[i - 1] + d] != oldrk[sa[i] + d]));
    }
    for (int i = 1, k = 0; i <= n; i++) {
        if (rk[i] == 0)
            continue;
        if (k)
            k--;
        while (s[i + k] == s[sa[rk[i] - 1] + k])
            k++;
        hei[rk[i]] = k, tot -= k;
    }
}

main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> s, s = ' ' + s, n = s.size() - 1, tot = n * (n + 1) / 2;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i] += a[i - 1], ans[i] = -1;
    SA(), build(1, n, 1);
    for (int i = 1; i <= n; i++) {
        if (i == 1)
            add(1, n - sa[i] + 1, 1, 1);
        else {
            int tot = qus(1, n - sa[i - 1] + 1, 1), lps = hei[i] ? qus(1, hei[i], 1) : 0;
            add(hei[i] + 1, hei[i] + 1, 1, tot - lps + 1);
            if (hei[i] < n - sa[i])
                add(hei[i] + 2, n - sa[i] + 1, 1, 1);
        }
        int l = sa[i], r = n;
        while (l ^ r) {
            int m = (l + r + 1) / 2, len = m - sa[i] + 1;
            if (tot - que(len) + 1 < a[m] - a[sa[i] - 1])
                r = m - 1;
            else
                l = m;
        }
        if (tot - que(l - sa[i] + 1) + 1 == a[l] - a[sa[i] - 1])
            ans[sa[i]] = l, res++;
    }
    cout << res << '\n';
    for (int i = 1; i <= n; i++)
        if (~ans[i])
            cout << i << ' ' << ans[i] << '\n';
}