Description

给你一个长度为\(n\)的序列，你要对它进行操作，规则如下

第\(i\)次操作时，找到区间\([1, n]\)中第\(i\)小的数的位置\(p_i\)，并翻转区间\([i, p_i]\)

最后输出操作序列\(p_i\)

Solution

很久没有做过\(Splay\)的题目了，来打个板子复习一下

我们可以把题意转换一下：第\(i\)次操作时，找到区间\([i, n]\)中最小的数的位置\(p_i\)，并翻转区间\([i, p_i]\)

然后这相当于就是一个排序 虽然我没用这个做法

我的做法特别简单粗暴，就是照着题意模拟

每次直接找整段区间最小值的位置，然后用\(Splay\)模拟题目的翻转，然后把这个最小值设为\(inf\)

\(p_i​\)序列就边操作边输出就可以了

Code

#include 
    
     using namespace std;#define fst first#define snd second#define mp make_pair#define squ(x) ((LL)(x) * (x))#define debug(...) fprintf(stderr, __VA_ARGS__)typedef long long LL;typedef pair
     
       pii;template
      
        inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }template
       
         inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }inline int read() {    int sum = 0, fg = 1; char c = getchar();    for (; !isdigit(c); c = getchar()) if (c == '-') fg = -1;    for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);    return fg * sum;}const int maxn = 1e5 + 10;const int inf = 1e9;int n, a[maxn];namespace Splay {    int rt;    struct node {        int f, son[2], v, s, sz;        bool rev;        node(): v(inf), s(inf) { }    }A[maxn];#define ls(x) A[x].son[0]#define rs(x) A[x].son[1]#define fa(x) A[x].f    inline void push_up(int x) { A[x].s = min(min(A[ls(x)].s, A[rs(x)].s), A[x].v), A[x].sz = A[ls(x)].sz + A[rs(x)].sz + 1; }    inline void push_down(int x) {        if (A[x].rev) {            swap(ls(x), rs(x));            A[ls(x)].rev ^= 1, A[rs(x)].rev ^= 1, A[x].rev = 0;        }    }    inline bool chk(int x) { return rs(fa(x)) == x; }    inline void link(int x, int y, int f) { fa(x) = y, A[y].son[f] = x; }    inline void rotate(int x) {        int f = fa(x), dx = chk(x), df = chk(f);        link(A[x].son[dx ^ 1], f, dx);        link(x, fa(f), df);        link(f, x, dx ^ 1);        push_up(f), push_up(x);    }    inline void splay(int x, int y) {        static int S[maxn]; S[S[0] = 1] = x;        for (int _x = x; _x; _x = fa(_x)) S[++S[0]] = _x;        while (S[0]) push_down(S[S[0]--]);        while (fa(x) != y) { if (fa(fa(x)) != y) rotate(chk(x) == chk(fa(x)) ? fa(x) : x); rotate(x); }        if (!y) rt = x; /**/    }    inline void build(int &x, int l, int r) {        if (l > r) return;        int mid = (l + r) >> 1;        A[x = mid].v = a[mid - 1];        build(ls(x), l, mid - 1), build(rs(x), mid + 1, r);        if (ls(x)) fa(ls(x)) = x;        if (rs(x)) fa(rs(x)) = x;        push_up(x);    }    inline int Rank(int k) {        int x = rt;        while (1) {            push_down(x);            int tot = A[ls(x)].sz + 1;            if (k == tot) break; /**/            if (k < tot) x = ls(x);            else x = rs(x), k -= tot;        }        return x;    }    inline void reverse(int x, int y) {        --x, ++y;        x = Rank(x), y = Rank(y);        splay(x, 0), splay(y, x);        A[ls(y)].rev ^= 1;    }    inline void change(int x) {        x = Rank(x);        A[x].v = inf;        while (x) push_up(x), x = fa(x);    }    inline int query() {        int x = rt, res = 0;        while (ls(x) || rs(x)) {            push_down(x);            if (A[x].v == A[x].s) { res += A[ls(x)].sz; break; } /**/            x = (A[ls(x)].s < A[rs(x)].s ? ls(x) : (res += A[ls(x)].sz + 1, rs(x)));        }        return res + 1;    }}int main() {#ifdef xunzhen    freopen("sort.in", "r", stdin);    freopen("sort.out", "w", stdout);#endif    static pii p[maxn];    n = read();    for (int i = 1; i <= n; i++) p[i] = mp(a[i] = read(), i);    sort(p + 1, p + n + 1);    for (int i = 1; i <= n; i++) a[p[i].snd] = i;    a[0] = a[n + 1] = inf;    Splay::build(Splay::rt, 1, n + 2);    for (int i = 2; i <= n + 1; i++) {        int x = Splay::query();        Splay::reverse(i, x);        Splay::change(i);        printf("%d%c", x - 1, i <= n ? ' ' : '\n');    }    return 0;}