bzoj【1552/3506】[Cerc2007]robotic sort

题目链接

Description

Input

输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。

Output

输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。 注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。

Sample Input

6

3 4 5 1 6 2

Sample Output

4 6 4 5 6 6

题解

这里使用指针的好处就显现出来了，每次找最小值直接就找到了。
然而很久以前读的题目这次直接做都忘记了还有重复的数这么一回事233.结果疯狂TLE。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define nd(x) (nil + (x))
using namespace std;
const int N = 100000 + 10;
struct data{
    int id, pos;
}a[N];
inline bool operator<(data a,data b) {return a.pos < b.pos; }
inline bool cmp(data a,data b) { return a.id < b.id || (a.id == b.id && a.pos < b.pos); }
struct Node{
    int a, rev, siz;
    Node *c[2], *f;

    int d() { return f->c[1] == this; }
    void sc(Node *x, int d) { (c[d] = x) -> f = this; }
    void pup() { siz = c[0]->siz + c[1]->siz + 1; }
    void pdw();
}nil[N], *root;

int id[N], pos[N], n;

void Node::pdw(){
    if(rev){
        c[0]->rev ^= 1;
        c[1]->rev ^= 1;
        swap(c[0], c[1]);
        rev = 0;
    }
}

inline void rotate(Node *x, Node *&k){
    int d = x->d();
    Node *p = x->f;
    p->sc(x->c[!d], d);
    if(p == k){
        x->f = k->f;
        k = x;
    }
    else p->f->sc(x, p->d());
    x->sc(p, !d);
    p->pup(); x->pup();
}

inline void splay(Node *x, Node *&k){
    for(Node *y; x != k;){
        if((y = x->f) != k) y->f->pdw();
        y->pdw(); x->pdw();
        if(y != k) (x->d() ^ y->d()) ? rotate(x, k) : rotate(y, k);
        rotate(x, k);
    }
}

Node *select(int k){
    Node *p = root;
    while(true){
        p->pdw();
        int t = p->c[0]->siz;
        if(k <= t) p = p->c[0];
        else if(k > t + 1) p = p->c[1], k -= t + 1;
        else break;
    }
    return p;
}

Node *build(int l, int r, Node *fa){
    if(l > r) return nil;
    if(l == r){
        Node *u = nd(l);
        u->c[0] = u->c[1] = nil; u->f = fa;
        u->siz = 1; u->a = a[l].id;
        return u;
    }
    int mid = (l + r) >> 1;
    Node *u = nd(mid);
    u->c[0] = build(l, mid-1, u); u->c[1] = build(mid+1, r, u);
    u->a = a[mid].id; u->f = fa; u->pup();
    return u;
}
inline void in(int &x){
    x = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    x *= f;
}
void init(){
    in(n);
    id[1] = 0; id[n+2] = n + 1;
    for(int i = 2; i <= n + 1; i++) in(a[i].id), a[i].pos = i;
    sort(a+2, a+n+2, cmp);
    for(int i = 2; i <= n + 1; i++) a[i].id = i - 1;
    sort(a+2, a+n+2);
    for(int i = 2; i <= n + 1; i++) pos[a[i].id] = i;
    nil->c[0] = nil->c[1] = nil->f = nil;
    root = build(1, n + 2, nil);
}
void solve(int k){
    Node *z = nd(pos[k]);
    splay(z, root);
    if(k != n) printf("%d ", z->c[0]->siz);
    else printf("%d\n", z->c[0]->siz);
    int rk = rk = z->c[0]->siz + 1;
    Node *x = select(k), *y = select(rk + 1);
    splay(x, root); splay(y, x->c[1]);
    z->rev ^= 1;
}
void outit(Node *p){
    if(p == nil) return;
    p->pdw();
    printf("%d %d %d %d\n", p->a, p->c[0]->a, p->c[1]->a, p->siz);
    outit(p->c[0]); outit(p->c[1]);
}
void work(){
    for(int p = 1; p <= n; p++)
        solve(p);
}

int main(){
    init();
    work();
    return 0;
}