「Loj 2312」「HAOI2017」供给侧改革 (Trie + 类似数论分块)

发表于 | 分类于 | | + s

Loj 2312
题意：给出一个 $n​$ 位随机 $01​$ 串，定义 $\text{data}(l,r)=\max(\text{LCP}(\text{Suf}_i,\text{Suf}_j)|i≠j,l≤i,j≤r)​$ 。
给出 $m​$ 个询问 $[l,r]​$ ，求
$$
\sum\limits_{i=l}^{r-1}\text{data}(i,r)
$$

题目说随机生成，那么估计LCP相同的概率为$({1\over 2})^{len} \cdot C^{2}_{r-l+1}$，在取$40$时，这个几率已经很小，我们直接对于每个后缀存前$40$个字符即可。考虑依次加入每个位置的后缀

我们发现对于一个区间$[l,r]$的答案，一定比$[l+1,r], [l+2,r], \dots , [r-1,r]$答案更大，因为他们是包含关系
那么我们可以运用这个单调性，还能发现答案是一块一块的，我们联想到数论分块的思想。

设$pos(i,j)$为$[1,i]$中后缀$\exists \text{LCP}=j$的最大位置。
那么求答案我们分成一块一块地求，具体看代码注释。

知识点：
1、单调性运用 (类似品酒大会从后往前求答案)
2、离线思想 (按某元素排序)

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 1;

    struct qry {
        int l, r, id;
        bool operator < (const qry &rhs) const {
            return r == rhs.r ? l < rhs.l : r < rhs.r;
        }
    } xw[MAXN];

    int n, Q, sz, ch[MAXN * 40][2], maxd[MAXN * 40], lst[MAXN * 40], pos[MAXN][55]; 
    // maxd_i i \in [0,40]：存在 LCP 长度为 i 的最大位置
    // lst_i： 访问该节点的最后子串(用于求maxd)
    // pos：如上述
    char s[MAXN];
    LL ans[MAXN];

    void insert(int l, int r) {
        int now = 0, p = 1;
        for (int i = l; i <= r; ++i, ++p) {
            int c = s[i] - '0';
            if (!ch[now][c]) ch[now][c] = ++sz;
            now = ch[now][c];

            maxd[p] = max(maxd[p], lst[now]); // 更新
            lst[now] = l; // 更新当前节点的信息
        }
    }

    void clean() {
        ms(maxd, 0), ms(lst, 0), ms(pos, 0), ms(ch, 0), sz = 0;
    }
    int solve() {

        clean();
        cin >> n >> Q;
        scanf("%s", s + 1);
        for (int i = 1; i <= Q; ++i) scanf("%d%d", &xw[i].l, &xw[i].r), xw[i].id = i;

        sort(xw + 1, xw + 1 + Q);

        for (int i = 1; i <= n; ++i) { // 求 pos
            insert(i, min(i + 40, n));
            for (int j = 1; j <= 40; ++j) pos[i][j] = maxd[j];
            pos[i][0] = i - 1;
        }

        int T = 1;
        for (int i = 1; i <= n; ++i) { // 枚举 r (其实这里求出来 pos 就不用离线的)
            while (T <= Q && xw[T].r == i) {
                int lst = 0;
                for (int j = 1; j <= 40; ++j) { // 扩展 LCP
                    if (pos[i][j]) {
                        if (pos[i][j] < xw[T].l) 
                            break ; // 已经不存在在区间 [l, r] 的更长 LCP
                        else 
                            ans[xw[T].id] += (pos[i][lst] - pos[i][j]) * lst, lst = j; // 加上这一块的答案，更新端点值
                    }
                }
                ans[xw[T].id] += (pos[i][lst] - xw[T].l + 1) * lst; // 加上最后一块答案
                ++T;
            }
        }

        for (int i = 1; i <= Q; ++i) printf("%lld\n", ans[i]);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------