SDOI2016 生成魔咒

#include <cstdio>
#include <cstring>

#include <algorithm>
#include <set>

using namespace std;

typedef long long ll;
typedef set<int> set_t;

const int N = 100010;

struct {
    int a, b, id;
} p[N], q[N];

struct node {
    int l, r, d;
    node *ls, *rs;

    int query(int l, int r) const;
};

int n;
int a[N], sa[N], rk[N], cnt[N], sorted[N], h[N], height[N];

node* build(int l, int r);

int main() {
    ll hsum = 0;
    scanf("%d", &n);
    for (int i = n; i; --i)
        scanf("%d", &a[i]);
    copy(a + 1, a + n + 1, sorted);
    sort(sorted + 1, sorted + n + 1);
    for (int i = 1; i <= n; ++i)
        a[i] = rk[i] = lower_bound(sorted + 1, sorted + n + 1, a[i]) - sorted;
    for (int l = 1; l <= n; l <<= 1) {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; ++i) {
            p[i].id = i;
            p[i].a = rk[i];
            p[i].b = (i + l) > n ? 0 : rk[i + l];
            ++cnt[p[i].b];
        }
        for (int i = 1; i <= n; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = n; i; --i)
            q[cnt[p[i].b]--] = p[i];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 1; i <= n; ++i)
            ++cnt[q[i].a];
        for (int i = 1; i <= n; ++i)
            cnt[i] += cnt[i - 1];
        for (int i = n; i; --i)
            p[cnt[q[i].a]--] = q[i];
        for (int i = 1; i <= n; ++i) {
            rk[p[i].id] = rk[p[i - 1].id];
            if (p[i].a != p[i - 1].a || p[i].b != p[i - 1].b)
                ++rk[p[i].id];
        }
    }
    for (int i = 1; i <= n; ++i)
        sa[rk[i]] = i;
    for (int i = 1; i <= n; ++i) {
        h[i] = h[i - 1] - 1;
        if (h[i] < 0)
            h[i] = 0;
        while (a[i + h[i]] == a[sa[rk[i] - 1] + h[i]])
            ++h[i];
    }
    for (int i = 1; i <= n; ++i)
        height[rk[i]] = h[i];
    node* seg = build(1, n);
    set<int> st;
    for (int i = n; i; --i) {
        set_t::iterator iter = st.insert(rk[i]).first, pre = iter, pst = iter;
        if (iter != st.begin()) {
            --pre;
            hsum += seg->query(*pre + 1, rk[i]);
            if (++pst != st.end()) {
                hsum += seg->query(rk[i] + 1, *pst);
                hsum -= seg->query(*pre + 1, *pst);
            }
        } else if (++pst != st.end())
            hsum += seg->query(rk[i] + 1, *pst);
        printf("%lld\n", (ll)(n - i + 1) * (n - i + 2) / 2 - hsum);
    }
    return 0;
}

node* build(int l, int r) {
    static node pool[N * 2];
    static node* top = pool;
    node* p = top;
    ++top;
    p->l = l;
    p->r = r;
    if (l == r) {
        p->d = height[l];
        return p;
    }
    int mid = (l + r) / 2;
    p->ls = build(l, mid);
    p->rs = build(mid + 1, r);
    p->d = min(p->ls->d, p->rs->d);
    return p;
}

int node::query(int l, int r) const {
    if (this->l == l && this->r == r)
        return d;
    if (r <= ls->r)
        return ls->query(l, r);
    if (l >= rs->l)
        return rs->query(l, r);
    return min(ls->query(l, ls->r), rs->query(rs->l, r));
}