BZOJ4698: Sdoi2008 Sandy的卡片(后缀数组 二分)

题意

题目链接

sol

不要问我为什么发两篇blog，就是为了骗访问量

后缀数组的也比较好想，先把所有位置差分，然后在height数组中二分就行了

数据好水啊

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
const int inf = 2333;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int t, n, m, a[maxn], id[maxn], rak[maxn], tp[maxn], tax[maxn], h[maxn], vis[maxn], sa[maxn], ti, mx;
void qsort() {
    for(int i = 0; i <= m; i++) tax[i] = 0;
    for(int i = 1; i <= n; i++) tax[rak[i]]++;
    for(int i = 1; i <= m; i++) tax[i] += tax[i - 1];
    for(int i = n; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];
}
void suffixsort() {
    for(int i = 1; i <= n; i++) rak[i] = a[i], tp[i] = i; 
    m = n + inf; qsort();
    for(int w = 1, p = 0; p < n; w <<= 1, m = p) { p = 0;
        for(int i = 1; i <= w; i++) tp[++p] = n - i + 1;
        for(int i = 1; i <= n; i++) if(sa[i] > w) tp[++p] = sa[i] - w;
        qsort(); swap(rak, tp); rak[sa[1]] = p = 1;
        for(int i = 2; i <= n; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p; 
    }
    for(int i = 1, k = 0; i <= n; i++) {
        if(k) k--; int j = sa[rak[i] - 1];
        while(a[i + k] == a[j + k]) k++;
        h[rak[i]] = k;
    }
}
bool check(int len) {
    ti++; int now = 0;
    for(int i = 1; i <= n; i++) {
        if(h[i] < len) {now = 0, ti++; continue;}
        if(vis[id[sa[i]]] != ti) vis[id[sa[i]]] = ti, now++; 
        if(now == t) return 1;
    }
    return 0;
}
int main() {
    //freopen("a.in", "r", stdin);
    t = read();
    for(int i = 1; i <= t; i++) {
        int num = read() - 1, pre = read(); a[++n] = i; id[n] = i; mx = max(mx, num + 1);
        while(num--) a[++n] = read() - pre + inf, pre = a[n] + pre - inf, id[n] = i;
    }
    suffixsort();
    int l = 1, r = mx, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    printf("%d", ans + 1);
    return 0;
}