题目描述

维护一个队列，初始为空。依次加入 n（1≤n≤105）个数 ai（-109≤ai≤109）,第 i（1≤i≤n）个数加入到当前序列第 bi（0≤bi≤当前序列长度）个数后面。输出最终队列。

输入格式

输入包含一个数 n（1≤n≤3×105），表示最终序列长度。

接下来 n 行，每行两个数 ai，bi，表示把 ai 放在当前序列第 bi 个数后面。

输出格式

输出 n 行，每行一个数，表示最终序列。

样例数据 1

输入

5
1 0
2 0
3 0
4 0
5 0

输出

5
4
3
2
1

题目分析

　　平衡树如splay/treap应该都能完成，这里给出无旋treap的做法。用无旋treap的话简直就是裸题，时间复杂度nlogn

code

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<algorithm>

#include<cmath>

using namespace std;

const int N = 3e5 + ;

int n;

#define SZ(x) (x?x->sze:0)

inline void wr(int);

struct node{

    node *lc, *rc;

    int pri, sze, val;

    inline node* upt(){

        sze = SZ(lc) + SZ(rc) + ;

        return this;

    }

    inline void print(){

        if(lc) lc->print();

        wr(val), putchar('\n');

        if(rc) rc->print();

    }

}pool[N], *tail = pool, *root = NULL;

inline int read(){

    int i = , f = ; char ch = getchar();

    for(; (ch < '' || ch > '') && ch != '-'; ch = getchar());

    if(ch == '-') f = -, ch = getchar();

    for(; ch >= '' && ch <= ''; ch = getchar())

        i = (i << ) + (i << ) + (ch - '');

    return i * f;

}

inline void wr(int x){

    if(x < ) putchar('-'), x = -x;

    if(x > ) wr(x / );

    putchar(x %  + '');

}

inline int Rand(){

    static int RAND_VAL = ;

    return RAND_VAL += RAND_VAL <<  | ;

}

inline node* newNode(int v){

    node *x = tail++;

    x->lc = x->rc = NULL;

    x->pri = Rand();

    x->val = v;

    x->sze = ;

    return x;

}

inline node* Merge(node *u, node *v){

    if(!u) return v->upt();

    if(!v) return u->upt();

    if(u->pri < v->pri){

        u->rc = Merge(u->rc, v);

        return u->upt();

    }

    else{

        v->lc = Merge(u, v->lc);

        return v->upt();

    }

}

inline void Split_k(node *u, int k, node *&x, node *&y){

    if(!u){

        x = y = NULL;

        return;

    }

    if(SZ(u->lc) < k){

        Split_k(u->rc, k - SZ(u->lc) - , x, y);

        u->rc = NULL, u->upt();

        x = Merge(u, x);

    }

    else{

        Split_k(u->lc, k, x, y);

        u->lc = NULL, u->upt();

        y = Merge(y, u);

    }

}

inline node* Insert(node *u, int k, int v){

    node *L, *R;

    Split_k(u, k, L, R);

    node *res = newNode(v);

    return Merge(Merge(L, res), R);

}

int main(){

    n = read();

    for(int i = ; i <= n; i++){

        int a = read(), b = read();

        root = Insert(root, b, a);

    }

    root->print();

    return ;

}

巴特西

【序列操作V】平衡树（无旋treap）