JCYZOJ 40 普通平衡树

普通平衡树

【题目描述】

写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入x数

2. 删除x数(若有多个相同的数，因只删除一个)

3. 查询x数的排名(若有多个相同的数，因输出最小的排名)

4. 查询排名为x的数

5. 求x的前驱(前驱定义为小于x，且最大的数)

6. 求x的后继(后继定义为大于x，且最小的数)

【输入格式】

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

【输出格式】

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

【样例输入】

10

1 106465

4 1

1 317721

1 460929

1 644985

1 84185

1 89851

6 81968

1 492737

5 493598

【样例输出】

106465

84185

492737

【数据范围】

对于50%的数据，n<=100

对于100%的数据，n<=100000

每个数不会超过int

Test 1
 使用内存 26416KB   总执行时间 0ms  结果 通过Accepted  
Test 2
 使用内存 26464KB   总执行时间 0ms  结果 通过Accepted  
Test 3
 使用内存 26480KB   总执行时间 0ms  结果 通过Accepted  
Test 4
 使用内存 26480KB   总执行时间 0ms  结果 通过Accepted  
Test 5
 使用内存 26480KB   总执行时间 0ms  结果 通过Accepted  
Test 6
 使用内存 26544KB   总执行时间 53ms 结果 错误答案Wrong Answer 
Test 7
 使用内存 26800KB   总执行时间 48ms 结果 错误答案Wrong Answer 
Test 8
 使用内存 26800KB   总执行时间 54ms 结果 错误答案Wrong Answer 
Test 9
 使用内存 26800KB   总执行时间 54ms 结果 错误答案Wrong Answer

平板电视确实很好用。。。。。。。。不过。。。。。。。似乎不支持相同数字。。。。。。。。。Orz

#include<cstdio>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
__gnu_pbds::tree<int,__gnu_pbds::null_type,std::less<int>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update> T;
int n;
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        switch(a){
            case 1:T.insert(b);break;
            case 2:T.erase(b);break;
            case 3:printf("%d\n",T.order_of_key(b)+1);break;
            case 4:printf("%d\n",*T.find_by_order(b-1));break;
            case 5:printf("%d\n",*--T.lower_bound(b));break;
            case 6:printf("%d\n",*T.upper_bound(b));break;
        }
    }
}

Log:2015-11-6支持相同元素完成

Test 1
 使用内存 26432KB   总执行时间 0ms  结果 通过Accepted  
Test 2
 使用内存 26480KB   总执行时间 0ms  结果 通过Accepted  
Test 3
 使用内存 26496KB   总执行时间 1ms  结果 通过Accepted  
Test 4
 使用内存 26496KB   总执行时间 0ms  结果 通过Accepted  
Test 5
 使用内存 26496KB   总执行时间 0ms  结果 通过Accepted  
Test 6
 使用内存 26560KB   总执行时间 154ms 结果 通过Accepted  
Test 7
 使用内存 27680KB   总执行时间 73ms 结果 通过Accepted  
Test 8
 使用内存 27696KB   总执行时间 55ms 结果 通过Accepted  
Test 9
 使用内存 27696KB   总执行时间 62ms 结果 通过Accepted 

#include<cstdio>
#include<fstream>
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define SN 10000
using namespace std;
__gnu_pbds::tree<double,int,std::less<double>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update> T;
int n;
void ins(int x){
	for(int i=1;i<=SN;i++)
		if(T.find(x+i/10000.0)==T.end()){
			T.insert(make_pair(x+i/10000.0,x));
			return;
		}
}

void era(int x){
	for(int i=1;i<=SN;i++)
		if(T.find(x+i/10000.0)!=T.end()){
			T.erase(x+i/10000.0);
			return;
		}
}
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int a,b;
        scanf("%d%d",&a,&b);

        switch(a){
            case 1:ins(b);break;
            case 2:era(b);break;
            case 3:printf("%d\n",T.order_of_key(b)+1);break;
            case 4:printf("%d\n",(*T.find_by_order(b-1)).second);break;
            case 5:printf("%d\n",(*--T.lower_bound(b)).second);break;
            case 6:printf("%d\n",(*T.upper_bound(b+0.999)).second);break;

        }
    }
}