武汉大学2020年大学生程序设计大赛决赛C

这里介绍一种失了智的算法。
这种算法基于插桩原理。我们每隔len插一个庄,我们发现所有长度为len的子串都会和一个桩相交。然后对于每个长度len我们只要能够通过n/lenlog(len)的复杂度算出所有长度为len的SAN值就可以在nloglog的时间复杂度内解决问题。
这里有三个子问题：
1.如何判断[l1,r1]和[l2,r2]这两个子串是否相等，这里采用字符串哈希O(n)预处理 O(单次取模)查询。
2.如何判断过当前桩的所有子串和过前一个桩的子串有递增SAN值的关系，这里采用二分加哈希的方式来解决O(n)预处理 O(log*单次取模)的复杂度，也可以采用两次后缀数组的方式O(nlog)预处理 O(1)查询会更快一些。
3.如何处理长度为len的子串中某些san值递增，某些san值清零的问题。线段树O(log)处理

即使如此，你仍然无法通过此题，因为整体复杂度是O(nloglog*单次取模复杂度)，%运算符是O(log)的，但是如今有取模黑科技可以比%运算符更加迅速，如此可以通过此题。

反正只要胆子大，常数卡卡就过了。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define lson rt * 2
#define rson rt * 2 + 1

typedef long long ll;

const int N = 1e5 + 100;
const int MOD = 1e9 + 7;
const int SZ = 200;

typedef  unsigned  long long ull;
typedef __uint128_t L;

struct FastMod {
  ull b, m;
  FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
  ull reduce(ull a) {
    return a - (ull)((L(m) * a) >> 64) * b;
  }
}F(MOD);

int tree[N * 4], laz[N * 4], flag[N * 4];

void push_down(int rt) {
    if (flag[rt]) {
        tree[lson] = laz[lson] = tree[rson] = laz[rson] = 0;
        flag[lson] = flag[rson] = 1;
        flag[rt] = 0;
    }
    laz[lson] += laz[rt];
    tree[lson] += laz[rt];
    laz[rson] += laz[rt];
    tree[rson] += laz[rt];
    laz[rt] = 0;
}

void insert(int rl, int rr, int l, int r, int rt) {
    if (rl == l && rr == r) {
        tree[rt]++;
        laz[rt]++;
        return;
    }
    push_down(rt);
    int m = (l + r) / 2;
    if (rr <= m) insert(rl, rr, l, m, lson);
    else if (m < rl) insert(rl, rr, m + 1, r, rson);
    else {
        insert(rl, m, l, m, lson);
        insert(m + 1, rr, m + 1, r, rson);
    }
    tree[rt] = max(tree[lson], tree[rson]) + laz[rt];
}

void clr(int rl, int rr, int l, int r, int rt) {
    if (rl == l && rr == r) {
        tree[rt] = laz[rt] = 0;
        flag[rt] = 1;
        return;
    }
    push_down(rt);
    int m = (l + r) / 2;
    if (rr <= m) clr(rl, rr, l, m, lson);
    else if (m < rl) clr(rl, rr, m + 1, r, rson);
    else {
        clr(rl, m, l, m, lson);
        clr(m + 1, rr, m + 1, r, rson);
    }
    tree[rt] = max(tree[lson], tree[rson]) + laz[rt];
}

int n;
char str[N];
ll pre[N], rff[N];

int qpow(int x, int n) {
    int r = 1;
    while (n > 0) {
        if (n & 1) r = 1LL * r * x % MOD;
        n /= 2;
        x = 1LL * x * x % MOD;
    }
    return r;
}

void init() {
    ll t = 1;
    for (int i = 1; i <= n; i++) {
        pre[i] = (pre[i - 1] + t * (str[i] - 'a')) % MOD;
        t = t * 26 % MOD;
    }
    int r = qpow(26, MOD - 2);
    rff[0] = 1;
    for (int i = 1; i <= n; i++) rff[i] = 1LL * rff[i - 1] * r % MOD;
}


/*int get(int l, int r) {
    if (r > n) return -1;
    int ans = 1LL * (pre[r] - pre[l - 1]) * rff[l - 1] % MOD;
    if (ans < 0) ans += MOD;
    return ans;
}*/


int get(int l, int r) {
    if (r > n) return -1; 
    int ans = F.reduce(F.reduce(pre[r] - pre[l - 1] + MOD) * rff[l - 1]);
    if (ans >= MOD) ans -= MOD;
    //printf("%d %d %d\n", l, r, ans);
    return ans;
}


void upd(int &x, int y) {
    if (y > x) x = y;
}

bool check(int l, int r, int d) {
    return get(l, r) == get(l + d, r + d);
}

int q1(int ql, int qr, int len) {
    if (str[ql] != str[ql - len]) return ql - 1;
    int m, l = ql, r = qr;
    while (r - l > 1) {
        m = (l + r) / 2;
        if (check(ql, m, -len)) l = m;
        else r = m;
    }
    if (check(ql, r, -len)) return r;
    return l;
}

int q2(int ql, int qr, int len) {
    if (str[qr] != str[qr - len]) return 1e9;
    int m, l = ql, r = qr;
    while (l < r) {
        m = (l + r) / 2;
        if (check(m, qr, -len)) r = m;
        else l = m + 1;
    }
    return l;
}

int main() {
    //freopen("0.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str + 1);
        n = strlen(str + 1);
        init();
        int ans = 0;
        for (int ma = 1; ma <= SZ && ma <= n; ma++) {
            for (int i = 1; i <= ma; i++) {
                int res = 1;
                for (int j = i; j <= n; j += ma) {
                    if (j - ma >= 1 && get(j - ma, j - 1) == get(j, j + ma - 1)) res++;
                    else {
                        upd(ans, res);
                        res = 1;
                    }
                }
                upd(ans, res);
            }
        }
        for (int sz = SZ + 1; sz <= n; sz++) {
            clr(1, sz, 1, sz, 1);
            for (int i = 2 * sz; i <= n; i += sz) {
                int l = q2(i - sz + 1, i, sz) - i + sz, r = q1(i, i + sz - 1, sz) - i + 1;
                if (r < l) {
                    clr(1, sz, 1, sz, 1);
                }
                else {
                    if (l > 1) clr(1, l - 1, 1, sz, 1);
                    if (r < sz) clr(r + 1, sz, 1, sz, 1);
                    insert(l, r, 1, sz, 1);
                }
                upd(ans, tree[1] + 1);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}