[bzoj3224][tyvj1728][普通平衡树] (pb_ds库自带红黑树)

Description

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

Input

第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数，表示对应答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

1.n的数据范围：n<=100000

2.每个数的数据范围：[-1e7,1e7]

数据如下http://pan.baidu.com/s/1jHMJwO2

 

pb_ds中红黑树500ms水过

#include <bits/stdc++.h>

#include <ext/pb_ds/tree_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

using namespace std;

using namespace __gnu_pbds;

struct pt{

    int first,second;

    pt(int x,int y) :first(x),second(y) {}

    bool operator<(const pt h)const{

        return first<h.first || (first==h.first&&second<h.second);

    }

    bool operator==(const pt h)const{

        return first==h.first&&second==h.second;

    }

};

typedef tree<pt,null_type,less< pt >,rb_tree_tag,tree_order_statistics_node_update> rbtree;

inline char Blue(){

    static char B[<<],*S=B,*T=B;

    if(S==T)T=(S=B)+fread(B,,<<,stdin);

    return *S++;

}

inline int Rin(){

    int x=,c=Blue(),f=;

    for(;c<||c>;c=Blue())

        if(!(c^))f=-;

    for(;c>&&c<;c=Blue())

        x=(x<<)+(x<<)+c-;

    return x*f;

}

int T,opt,x;

map<int,int>s;

rbtree t;

int main(){

    T=Rin();

    while(T--){

        opt=Rin(),x=Rin();

        switch(opt){

            case :t.insert(pt(x,s[x]++));break;

            case :t.erase(pt(x,--s[x]));break;

            case :

                printf("%d\n",t.order_of_key(pt(x,))+);

                break;

            case :

                printf("%d\n",t.find_by_order(x-)->first);

                break;

            case :

                printf("%d\n",t.find_by_order(t.order_of_key(pt(x,))-)->first);

                break;

            case :

                printf("%d\n",t.find_by_order(t.order_of_key(pt(x,s[x]-))+(t.find(pt(x,))==t.end()?:))->first);

                break;

            default:break;

        }

    }

    return ;

}