hdu 3436 Queuejumpers(Splay Tree)

acm.hdu.edu.cn/showproblem.php?pid=3436

　　中等难度的数据结构题，不过数据范围大，所以要hash操作过的数列。1y～

　　题意就像题目一样，模拟一队人，其中有人插队，询问某个时刻，第x个人的编号或编号为x的人的位置。

代码如下：

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

struct Node {
    int l, r;
    int cnt;
    Node *c[2], *p;

    Node (int _cnt = 0, int _l = 0, int _r = -1) {
        l = _l;
        r = _r;
        cnt = _cnt;
        c[0] = c[1] = p = NULL;
    }
} *Null, *Root, *Head;

void up(Node *rt) {
    rt->cnt = rt->c[0]->cnt + rt->c[1]->cnt + (rt->r - rt->l + 1);
}

void rotate(Node *x, bool right) {
    Node *y = x->p;

    y->c[!right] = x->c[right];
    if (x->c[right] != Null) {
        x->c[right]->p = y;
    }
    x->p = y->p;
    if (y->p != Null) {
        if (y->p->c[0] == y) {
            y->p->c[0] = x;
        } else {
            y->p->c[1] = x;
        }
    }
    x->c[right] = y;
    y->p = x;
    up(y);

    if (Root == y) Root = x;
}

void splay(Node *x, Node *f) {
    while (x->p != f) {
        if (x->p->p == f) {
            if (x->p->c[0] == x) rotate(x, 1);
            else rotate(x, 0);
        } else {
            Node *y = x->p, *z = y->p;

            if (z->c[0] == y) {
                if (y->c[0] == x) {
                    rotate(y, 1);
                    rotate(x, 1);
                } else {
                    rotate(x, 0);
                    rotate(x, 1);
                }
            } else {
                if (y->c[0] == x) {
                    rotate(x, 1);
                    rotate(x, 0);
                } else {
                    rotate(y, 0);
                    rotate(x, 0);
                }
            }
        }
    }

    up(x);
}

const int inf = 0x7f7f7f7f;

void initSplay() {
    Null = new Node();
    Root = Head = new Node(1, 0, 0);

    Root->p = Root->c[0] = Null;
    Root->c[1] = new Node(1, inf, inf);
    Root->c[1]->p = Root;
    Root->c[1]->c[0] = Root->c[1]->c[1] = Null;
    up(Root);
}

void in_tra(Node *rt) {
    if (rt == Null) {
        return ;
    }
    in_tra(rt->c[0]);
    printf("%d %d %d %d %d %d %d\n", rt->l, rt->r, rt->cnt, rt, rt->p, rt->c[0], rt->c[1]);
    in_tra(rt->c[1]);
}

const int maxn = 100005;
const int HASH = 0x55555555;
const int hashMod = 400009;

char op[maxn][6];
int num[maxn], hash[hashMod], hashPos[hashMod];

void initHash() {
    memset(hashPos, 0, sizeof(hashPos));
}

void insHash(int x, int pos) {
    int p = (x ^ HASH) % hashMod;

    while (hash[p] != x && hashPos[p]) {
        p++;
        if (p >= hashMod) p -= hashMod;
    }

    hash[p] = x;
    hashPos[p] = pos;
}

int getHash(int x) {
    int p = (x ^ HASH) % hashMod;

    while (hash[p] != x && hashPos[p]) {
        p++;
        if (p >= hashMod) p -= hashMod;
    }

    return hashPos[p];
}

Node *rec[maxn << 1];

void insSplay(Node *x) {
    x->c[1] = Root->c[1];
    Root->c[1]->p = x;
    Root->c[1] = x;
    x->p = Root;
    x->c[0] = Null;

    splay(x, Null);
}

void build(int n, int m) {
    set<int> used;

    initSplay();
    used.clear();
    for (int i = 0; i < m; i++) {
        scanf("%s%d", op[i], &num[i]);
        if (op[i][0] == 'T' || op[i][0] == 'Q') {
            used.insert(num[i]);
        }
    }

    int last = 0, cnt = 0;

    for (set<int>::iterator si = used.begin(); si != used.end(); si++) {
//        printf("%d\n", *si);
        if (last + 1 < *si) {
            rec[++cnt] = new Node(1, last + 1, *si - 1);
//            printf("add %d %d\n", last + 1, *si - 1);
            insSplay(rec[cnt]);
        }
        rec[++cnt] = new Node(1, *si, *si);
//        printf("add %d\n", *si);
        insSplay(rec[cnt]);

        insHash(*si, cnt);
        last = *si;
    }
    if (last < n) {
        rec[++cnt] = new Node(1, last + 1, n);
//        printf("add %d %d\n", last + 1, n);
        insSplay(rec[cnt]);
    }

//    printf("cnt %d\n", cnt);
//    puts("built!");
}

int getPos(int x) {
    Node *rt = rec[getHash(x)];

    splay(rt, Null);

    return rt->c[0]->cnt;
}

int getPer(int pos) {
    Node *p = Root;

    pos++;
    while (true) {
        int cnt = p->c[0]->cnt;

        if (cnt + 1 <= pos && pos <= cnt + (p->r - p->l + 1)) {
            pos -= cnt;

            return p->l + pos - 1;
        } else if (pos <= cnt) {
//            puts("left");
            p = p->c[0];
        } else {
//            puts("right");
            pos -= cnt + (p->r - p->l + 1);
            p = p->c[1];
        }
    }
}

Node *preNode(Node *x) {
    splay(x, Null);
    x = x->c[0];
    while (x->c[1] != Null) x = x->c[1];

    return x;
}

Node *postNode(Node *x) {
    splay(x, Null);
    x = x->c[1];
    while (x->c[0] != Null) x = x->c[0];

    return x;
}

void Top(int x) {
    x = getHash(x);
//    printf("x %d\n", x);

    Node *pl = preNode(rec[x]);
    Node *pr = postNode(rec[x]);

    splay(pl, Null);
    splay(pr, pl);

    // cut node
    Node *tmp = pr->c[0];
    pr->c[0] = Null;
    splay(pr, Null);
    // top node
    splay(Head, Null);
    insSplay(tmp);
}

void process(int m) {
    for (int i = 0; i < m; i++) {
        switch (op[i][0]) {
            case 'T':
//                puts("Top");
                Top(num[i]);
                break;
            case 'Q':
//                puts("Query");
                printf("%d\n", getPos(num[i]));
                break;
            case 'R':
//                puts("Rank");
                printf("%d\n", getPer(num[i]));
                break;
        }
    }
}

int main() {
    int T;

//    freopen("in", "r", stdin);
    scanf("%d", &T);
    for (int i = 1; i <= T; i++) {
        int n, m;

        scanf("%d%d", &n, &m);
        build(n, m);
        printf("Case %d:\n", i);
        process(m);
    }

    return 0;
}

——written by Lyon