BZOJ4516: [Sdoi2016]生成魔咒(后缀数组 set RMQ)

时间：2022-04-14 12:23:03

题意

题目链接

Sol

毒瘤SDOI 终于有一道我会做的题啦qwq

首先，本质不同的子串的个数 $ = \frac{n(n + 1)}{2} - \sum height[i]$

把原串翻转过来，每次就相当于添加一个后缀

然后直接用set xjb维护一下前驱后继就行了

时间复杂度：\(O(nlogn)\)

// luogu-judger-enable-o2

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define sit set<int>::iterator

#define LL long long

using namespace std;

const int MAXN = 2e5 + 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 N, M, L, rak[MAXN], tax[MAXN], tp[MAXN], sa[MAXN], H[MAXN], f[MAXN][20], lg2[MAXN], s[MAXN], date[MAXN], ans[MAXN];

set<int> st;

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] = s[i], tp[i] = i; M = 233; 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(tp, rak); 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(s[i + k] == s[j + k]) k++;

        H[rak[i]] = k;

    }

}

void Pre() {

    for(int i = 1; i <= N; i++) f[i][0] = H[i];

    for(int j = 1; j <= 17; j++)

        for(int i = 1; i + (1 << j) - 1 <= N; i++) f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

}

int Query(int x, int y) {

    if(x > y) swap(x, y); x++;

    int k = lg2[y - x + 1];

    return min(f[x][k], f[y - (1 << k) + 1][k]);

}

void Des() {

    sort(date + 1, date + N + 1);

    int num = unique(date + 1, date + N + 1) - date - 1;

    for(int i = 1; i <= N; i++) s[i] = lower_bound(date + 1, date + num + 1, s[i]) - date;

    reverse(s + 1, s + N + 1);

}

int main() {

    lg2[1] = 0; for(int i = 2; i <= MAXN - 1; i++) lg2[i] = lg2[i >> 1] + 1;

    N = read();

    for(int i = 1; i <= N; i++) s[i] = date[i] = read();

    Des();

    SuffixSort(); Pre();

    st.insert(0); st.insert(N + 1);

    LL now = 0; st.insert(rak[N]); ans[N] = 1;

    printf("%lld\n", 1);

    for(int i = N - 1; i >= 1; i--) {

        sit nxt = st.upper_bound(rak[i]), pre;

        if(*nxt == 0) pre = st.begin();

        else pre = --nxt, nxt++;

    //  printf("%d %d\n", *pre, *nxt);

        if(*pre != 0 && *nxt != N + 1) now -= Query(*pre, *nxt);

        if(*pre != 0 && *pre != N + 1) now += Query(*pre, rak[i]);

        if(*nxt != 0 && *nxt != N + 1) now += Query(rak[i], *nxt);

        printf("%lld\n", 1ll * (N - i + 1) * ((N - i + 1) + 1) / 2 - now);

        st.insert(rak[i]);

    }

    return 0;

}

/*

4

1 2 3 3

3

1 3 1

*/

相关文章