「Bzoj 2754」「SCOI2012」喵星球上的点名 (后缀数组+二分+莫队+离线)

BZOJ 2754
题意:见上。

考虑将所有名字姓和名用特殊符号链接,然后构造后缀数组

引理1:

$S_2$ 是 $S_1$ 的子串当且仅当 $\exists S_1$的后缀和$S_2$的$height=len(S_2)$

引理2:

后缀数组的$SA$数组具有二分单调性,即确定了前$i-1$位,可以在$SA$数组中二分第$i$位的位置

用引理1或者引理2(代码使用2)用上二分可以找出一个询问在$SA$数组上的区间范围,即这个区间上的后缀的前缀都有这个询问串。
这里二分要用左闭右闭区间的,用左闭右开会莫名GG
那么现在问题转化为求区间的不同颜色的个数,显然莫队裸题。
第二问的话,在莫队的时候,如果第一次加入某种颜色,则加上当前最大可能的个数,然后某种颜色被完全删除后就减掉当前最大可能的个数

知识点
1、二分
2、后缀数组从1开始

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#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 = 200000 + 5;

    int n, m, lmt, which[MAXN], tmp1, tmp2;
    int a[MAXN], bl[MAXN], blolen;
    int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
    int ans1[MAXN], ans2[MAXN];

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

    void build() {

        for (int i = 1; i <= m; ++i) tax[i] = 0;
        for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
        for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
        for (int i = n; i; --i) SA[tax[rk[i]]--] = i;

        for (int k = 1; k <= n; k *= 2) {
            int p = 0;
            for (int i = n - k + 1; i <= n; ++i) tp[++p] = i;
            for (int i = 1; i <= n; ++i) if (SA[i] > k) tp[++p] = SA[i] - k;

            for (int i = 1; i <= m; ++i) tax[i] = 0;
            for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;
            for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
            for (int i = n; i; --i) SA[tax[rk[tp[i]]]--] = tp[i];

            swap(rk, tp), p = 1, rk[SA[1]] = 1;
            for (int i = 2; i <= n; ++i) {
                rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
            }

            if (p >= n) break ;
            m = p;

        }
    }

    int l, r, cnt, tax_md[MAXN];
    void inc(int pos, int whw) {
        if (++tax_md[which[SA[pos]]] == 1) {
            ++cnt, ans2[which[SA[pos]]] += tmp2 - whw + 1;
        }
    }
    void dec(int pos, int whw) {
        if (--tax_md[which[SA[pos]]] == 0) {
            --cnt, ans2[which[SA[pos]]] -= tmp2 - whw + 1;
        }
    }

    void clean() {
           n = 0, lmt = 10000 + 2, m = 10000 + 2;
           ms(ans1, 0), ms(ans2, 0);
    }
    int solve() {

        clean();

        scanf("%d%d", &tmp1, &tmp2);
        for (int len, i = 1; i <= tmp1; ++i) {

            scanf("%d", &len);
            for (int x, j = 1; j <= len; ++j) {
                scanf("%d", &x);
                a[++n] = x, which[n] = i;
            }
            a[++n] = lmt;

            scanf("%d", &len);
            for (int x, j = 1; j <= len; ++j) {
                scanf("%d", &x);
                a[++n] = x, which[n] = i;
            }
            a[++n] = lmt;

        }

        build();

        blolen = sqrt(n);
        for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blolen + 1;

        for (int len, i = 1; i <= tmp2; ++i) { // 在 SA 数组中二分
            scanf("%d", &len);
            int L = 1, R = n; 
            for (int x, j = 1; j <= len; ++j) { // 找加入第 i 位后符合的下界
                scanf("%d", &x);

                int l = L, r = R, ltmp;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (a[SA[mid] + j - 1] < x) l = mid + 1; else r = mid - 1;
                }
                ltmp = l;

                l = L, r = R;
                while (l <= r) { // 找加入第 i 位后符合的上界
                    int mid = (l + r) >> 1;
                    if (a[SA[mid] + j - 1] <= x) l = mid + 1; else r = mid - 1; 
                }
                L = ltmp, R = r;

            }
            if (L <= R) xw[i] = (qry){L, R, i};
        } 

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

        l = 1, r = 0, cnt = 0;
        for (int i = 1; i <= tmp2; ++i) {

            while (l > xw[i].l) inc(l - 1, i), --l;
            while (r < xw[i].r) inc(r + 1, i), ++r;
            while (l < xw[i].l) dec(l, i), ++l;
            while (r > xw[i].r) dec(r, i), --r;

            ans1[xw[i].id] = cnt; 

        }

        for (int i = 1; i <= tmp2; ++i) printf("%d\n", ans1[i]);
        for (int i = 1; i <= tmp1; ++i) printf("%d ", ans2[i]);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
test 1
2 1

3
1 2 1
3
1 2 1

3
1 2 2
3
1 2 2

3
1 2 1

test 2
2 1

3
1 2 0
3
1 2 0

3
1 2 0
3
1 2 0

3
1 2 1
*/
------ 本文结束 ------