Robotic Sort

题目链接

[HDU 1890] Robotic Sort

题解

高档题。题意大概是每次将一段连续的区间翻转,使得最后的序列有序,输出翻转过程。
Splay模板题,直接套即可。

代码

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 1 << 30;
const int maxn = 100005;

int order[maxn], input[maxn], siz[maxn], ch[maxn][2], rev[maxn], pre[maxn], id[maxn];
int root, top, n, r, ans;

bool cmp(int a, int b) {
    if (input[a] != input[b])
        return input[a]<input[b];
    return a<b;
}

inline void insert(int &x, int p) {
    x = ++top;
    siz[x] = 1;
    ch[x][0] = ch[x][1] = 0;
    pre[x] = p;
    rev[x] = 0;
}

inline void pushup(int x) {
    siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}

inline void pushdown(int x) {
    if (rev[x]) {
        swap(ch[x][0], ch[x][1]);
        rev[ch[x][0]] ^= 1;
        rev[ch[x][1]] ^= 1;
        rev[x] = 0;
    }
}

inline void build(int &x, int l, int r, int p) {
    int mid = (l + r) >> 1;
    insert(x, p);
    id[mid] = top;
    if (l<mid) build(ch[x][0], l, mid - 1, x);
    if (r>mid) build(ch[x][1], mid + 1, r, x);
    pushup(x);
}

inline void rotate(int x, int kind) {
    int y = pre[x];
    pushdown(y);
    pushdown(x);
    ch[y][!kind] = ch[x][kind];
    pre[ch[x][kind]] = y;
    if (pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x;
    pre[x] = pre[y];
    ch[x][kind] = y;
    pre[y] = x;
    pushup(y);
}

inline void splay(int x, int goal)
{
    while (pre[x] != goal) {
        if (pre[pre[x]] == goal) {
            pushdown(pre[x]);
            pushdown(x);
            rotate(x, ch[pre[x]][0] == x);
        }
        else {
            pushdown(pre[pre[x]]);
            pushdown(pre[x]);
            pushdown(x);
            int y = pre[x];
            int kind = ch[pre[y]][0] == y;
            if (ch[y][kind] == x) {
                rotate(x, !kind);
                rotate(x, kind);
            }
            else {
                rotate(y, kind);
                rotate(x, kind);
            }
        }
    }
    pushup(x);
    if (goal == 0) root = x;
}

inline void findLeft(int x) {
    pushdown(x);
    siz[x]--;
    if (ch[x][1] == 0) {
        int kind = ch[pre[x]][1] == x;
        pre[ch[x][0]] = pre[x];
        ch[pre[x]][kind] = ch[x][0];
        ch[x][0] = ch[root][0];
        ch[x][1] = ch[root][1];
        pre[ch[x][0]] = pre[ch[x][1]] = x;
        pre[x] = 0;
        root = x;
        pushup(x);
    }
    else findLeft(ch[x][1]);
}

inline int update(int r)
{
    splay(r, 0);
    int ans = siz[ch[r][0]] + 1;
    rev[ch[r][0]] ^= 1;
    if (ch[r][0] == 0) {
        ch[0][1] = ch[r][1];
        pre[ch[r][1]] = 0;
    }
    else findLeft(ch[r][0]);
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    for (cin >> n; n; cin >> n) {
        for (int i = 0; i < n; i++) {
            cin >> input[i];
            order[i] = i;
        }
        root = 1;
        top = 0;
        siz[0] = ch[0][0] = ch[0][1] = pre[0] = rev[0] = 0;
        build(ch[0][1], 0, n - 1, 0);

        sort(order, order + n, cmp);
        for (int i = 0; i<n; i++) {
            r = id[order[i]];
            ans;
            ans = update(r);
            printf("%d%c", ans + i, ((i == n - 1) ? '\n' : ' '));
        }
    }
}

标签: data structures

添加新评论