题解

#include <bits/stdc++.h>
using namespace std;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
const int N = 1e5 + 10;
struct node {
    int ls, rs, val, mn, siz, rev, rnd;
} tr[N];
int rt, trlen;

int newd(int v) {
    tr[++trlen] = {0, 0, v, v, 1, 0, rand()};
    return trlen;
}

void pushup(int p) {
    tr[p].siz = tr[lc(p)].siz + tr[rc(p)].siz + 1;
    tr[p].mn = tr[p].val;
    if (lc(p)) tr[p].mn = min(tr[p].mn, tr[lc(p)].mn);
    if (rc(p)) tr[p].mn = min(tr[p].mn, tr[rc(p)].mn);
}

void pushdown(int p) {
    if (!tr[p].rev) return;
    swap(lc(p), rc(p));
    tr[lc(p)].rev ^= 1;
    tr[rc(p)].rev ^= 1;
    tr[p].rev = 0;
}

void split(int p, int k, int &x, int &y) {
    if (p == 0) {
        x = y = 0;
        return;
    }
    pushdown(p);
    if (tr[lc(p)].siz < k) {
        x = p;
        split(rc(p), k - tr[lc(p)].siz - 1, rc(x), y);
    } else {
        y = p;
        split(lc(p), k, x, lc(y));
    }
    pushup(p);
}

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr[x].rnd < tr[y].rnd) {
        pushdown(x);
        rc(x) = merge(rc(x), y);
        pushup(x);
        return x;
    } else {
        pushdown(y);
        lc(y) = merge(x, lc(y));
        pushup(y);
        return y;
    }
}

int getrnk(int p) {
    int k = 0;
    while (1) {
        pushdown(p);
        if (lc(p) && tr[p].mn == tr[lc(p)].mn) {
            p = lc(p);
        } else if (rc(p) && tr[p].mn == tr[rc(p)].mn) {
            k += tr[lc(p)].siz + 1;
            p = rc(p);
        } else {
            return k + tr[lc(p)].siz + 1;
        }
    }
}

pair<int, int> v[N];
int vv[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &v[i].first);
        v[i].second = i;
    }
    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; ++i) {
        vv[v[i].second] = i;
    }

    // Initialize the treap
    rt = trlen = 0;
    for (int i = 1; i <= n; ++i) {
        rt = merge(rt, newd(vv[i]));
    }

    for (int i = 1; i <= n; ++i) {
        int k = getrnk(rt);
        int x, y, z;
        split(rt, k, x, y);
        split(x, k - 1, x, z);
        tr[x].rev ^= 1; // reverse the segment
        rt = merge(x, y);
        printf("%d ", k + i - 1);
    }

    return 0;
}