BZOJ1552 [CERC2007]robotic sort & BZOJ3506 [CQOI2014]排序机械臂

2015.02.22 15:10 Sun| 2 visits oi_2015| 2015_刷题日常| Text

Solution

这个题本来准备是 WC 之前的 Splay 复习 + 练手来着,结果断断续续写了大半个月 QAQ。开始把这道题写傻了。我果然很弱啊……

其实这道题还算好写哈。Splay 里面只需要额外记录子树中的最小值和旋转标记就好啦~最开始需要加上一个简单的离散化。为什么那么多人都写成了超过两百行的长代码 x_x。

Code

#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define N 100005

int n, a[N];
pair<int, int> b[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct splay_tree
{
    struct node
    {
        int size, mint, val; bool rev; node *son[2], *par;

        node() : size(), mint(), val(), rev(), son(), par() {}
        node(int _val)
        : size(1), mint(_val), val(_val), rev(), son(), par() {};

        inline bool check() { return par->son[1] == this; }

        inline void combine(node *x, int d) { son[d] = x; x->par = this; }

        inline void reverse() { rev ^= 1; swap(son[0], son[1]); }

        inline void pushup()
        {
            pushdown();
            size = son[0]->size + son[1]->size + 1;
            mint = min(val, min(son[0]->mint, son[1]->mint));
        }

        inline void pushdown()
        {
            if (rev) son[0]->reverse(), son[1]->reverse(), rev ^= 1;
        }
    } *root, *nil;

    splay_tree() { nil = new node(inf); nil->size = 0; }

    void build_tree()
    {
        root = build(0, n + 1);
        root->par = nil;
    }

    node *build(int l, int r)
    {
        if (l > r) return nil;
        int mid = (l + r) >> 1;
        node *re = new node(a[mid]);
        re->combine(build(l, mid - 1), 0);
        re->combine(build(mid + 1, r), 1);
        re->pushup(); return re;
    }

    void rotate(node *x)
    {
        node *k = x->par; int d = !x->check();
        k->combine(x->son[d], d ^ 1);
        k->par->combine(x, k->check());
        x->combine(k, d);
        k->pushup(); x->pushup();
    }

    void splay(node *x, node *aim)
    {
        while (x->par != aim)
        {
            if (x->par->par != aim)
                x->check() ^ x->par->check() ?
                    rotate(x) : rotate(x->par);
            rotate(x);
        }
        if (aim == nil) root = x;
    }

    node *find(node *x, int t)
    {
        x->pushdown();
        if (t <= x->son[0]->size)
            return find(x->son[0], t);
        t -= x->son[0]->size;
        return t == 1 ? x : find(x->son[1], t - 1);
    }

    node *getmin(node *x)
    {
        x->pushdown();
        if (x->mint == x->val) return x;
        return getmin(x->son[x->son[0]->mint > x->son[1]->mint]);
    }

    int findmin(int t)
    {
        splay(getmin(root), nil);
        int re = root->son[0]->size;
        root->val = inf; root->pushup();
        splay(find(root, t), nil);
        splay(find(root, re + 2), root);
        root->son[1]->son[0]->reverse();
        return re;
    }

    void print(node *x)
    {
        if (x == nil) return;
        print(x->son[0]);
        cout << x->val << ' ' << x->size << ' ' << x->mint << endl;
        print(x->son[1]);
    }
};

splay_tree s;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        b[i].first = read(), b[i].second = i;
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        a[b[i].second] = i;
    a[0] = a[n + 1] = inf;
    s.build_tree();
    for (int i = 1; i <= n; ++i)
        printf("%d%c", s.findmin(i), " \n"[i == n]);
}