bzoj3224 Tyvj1728 普通平衡树_AaronPolaris的博客-程序员秘密

3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 7650 Solved: 3223
[ Submit][ Status][ Discuss]

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

Source

平衡树

平衡树模板题

注意Treap的删除操作的写法！！！

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define N 100005
#define inf 1000000000
using namespace std;
int n,rt,tot;
int rnd[N],l[N],r[N],v[N],w[N],sz[N];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void lturn(int &k)
{
	int tmp=r[k];r[k]=l[tmp];l[tmp]=k;
	sz[tmp]=sz[k];sz[k]=sz[l[k]]+sz[r[k]]+w[k];
	k=tmp;
}
void rturn(int &k)
{
	int tmp=l[k];l[k]=r[tmp];r[tmp]=k;
	sz[tmp]=sz[k];sz[k]=sz[l[k]]+sz[r[k]]+w[k];
	k=tmp;
}
void insert(int &k,int x)
{
	if (!k){k=++tot;v[k]=x;sz[k]=w[k]=1;l[k]=r[k]=0;rnd[k]=rand();return;}
	sz[k]++;
	if (v[k]==x) w[k]++;
	else if (v[k]>x){insert(l[k],x);if (rnd[l[k]]<rnd[k]) rturn(k);}
	else{insert(r[k],x);if (rnd[r[k]]<rnd[k]) lturn(k);}
}
void del(int &k,int x)//一定要记住这里面sz[k]--的位置!!! 
{
	if (v[k]==x)
	{
		if (w[k]>1) w[k]--,sz[k]--;
		else if (!l[k]||!r[k]) k=l[k]+r[k];
		else if (rnd[l[k]]<rnd[r[k]]) rturn(k),del(k,x);
		else lturn(k),del(k,x);
		return;
	}
	sz[k]--;
	if (x<v[k]) del(l[k],x);
	else del(r[k],x);
}
int getrnk(int k,int x)
{
	if (v[k]==x) return sz[l[k]]+1;
	else if (x<v[k]) return getrnk(l[k],x);
	else return getrnk(r[k],x)+sz[l[k]]+w[k];
}
int getkth(int k,int x)
{
	if (sz[l[k]]<x&&sz[l[k]]+w[k]>=x) return v[k];
	else if (x<=sz[l[k]]) return getkth(l[k],x);
	else return getkth(r[k],x-sz[l[k]]-w[k]);
}
int pre(int k,int x)
{
	if (!k) return -inf;
	if (x<=v[k]) return pre(l[k],x);
	else
	{
		int tmp=pre(r[k],x);
		return tmp==-inf?v[k]:tmp;
	}
}
int suc(int k,int x)
{
	if (!k) return inf;
	if (x>=v[k]) return suc(r[k],x);
	else
	{
		int tmp=suc(l[k],x);
		return tmp==inf?v[k]:tmp;
	}
}
int main()
{
	srand(233);
	n=read();
	F(i,1,n)
	{
		int opt=read(),x=read();
		if (opt==1) insert(rt,x);
		else if (opt==2) del(rt,x);
		else if (opt==3) printf("%d\n",getrnk(rt,x));
		else if (opt==4) printf("%d\n",getkth(rt,x));
		else if (opt==5) printf("%d\n",pre(rt,x));
		else printf("%d\n",suc(rt,x));
	}
	return 0;
}

本文链接：https://blog.csdn.net/AaronGZK/article/details/51855033

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

安卓ListView的使用_apple_51426592的博客-程序员秘密

listview是一个以垂直方式在项目中显示视图的列表。是一种不能实现确定视图中的内容的适配器视图（adapter view）。数据和视图的绑定，需要通过继承ListViewAdapter接口的适配器实现。确保当上下滚动的时候，能够动态刷新视图内容。通常我们都会自定义一个继承自BaseAdapter(已继承ListViewAdapter)，ArrayAdapter(继承自BaseAdapter),SimpleAdapter(继承自BaseAdapter)的类，重写getView()方法，实现自己想要的功能。

Spark 初识_不二人生的博客-程序员秘密

从今天开始我们进入数据仓库的查询引擎篇了，前面我们已经写了大量的文章介绍Hive,具体你可以看hive 的专栏,而且关于工具这一块我们的重点就在hive 上，后面关于spark、presto、impala、clickHouse的介绍都不会像前面这样细了，因为我们的重点是在数仓建设的方法论上面，而不是工具上面。Spark 是一种高效且多用途的集群计算平台。换句话说，Spark 是一种开源的，大规模数据处理引擎。它提供了一整套开发 API，包括流计算、机器学习或者SQL。Spark 支持批处理和流处理。批处理指

270-FPGA V7卡学习资料：VC709E 增强版基于FMC接口的Xilinx Vertex-7 FPGA V7 XC7VX690T PCIeX8 接口卡_xc7vx690t开发板原理图_hexiaoyan827的博客-程序员秘密

VC709E 增强版基于FMC接口的Xilinx Vertex-7 FPGA V7 XC7VX690T PCIeX8 接口卡一、板卡概述本板卡基于Xilinx公司的FPGA XC7VX690T-FFG1761 芯片，支持PCIeX8、64bit DDR3容量2GByte，HPC的FMC连接器，板卡支持各种接口...

如何定义全局变量_caoeryingzi的博客-程序员秘密

<br />比较规范的是，先定义一个Glbs.h，把所有的全局变量原始定义放进去。然后定义一个Externs.h，把你先前定义在Glbs.h中的变量都加上extern。注意：如果你在Glbs.h中设置了初值，那么在Externs.h中就不要加值了。然后调用时，第一次调用的＃i nclude Glbs.h，以后调用的＃i nclude externs.h<br /> <br /> <br />老公，成功地定义了一个全局、h文件，而后通过宏定义，一个h文件就解决这个问题了。只是，在第一次调用时，调用前要加一句话

org.apache.hadoop.fs.FSInputChecker - Problem opening checksum file_鸭梨山大哎的博客-程序员秘密

WARN org.apache.hadoop.fs.FSInputChecker - Problem opening checksum file: /common/nlp/data/dictionary/custom/CustomDictionary.txt.bin. Ignoring exception:java.io.EOFExceptionat java.io.DataInputStream.readFully(DataInputStream.java:197)at java.io.Dat

【imx6ul】从头搭建imx6ul开发环境（uboot、内核编译及烧入、mfgtools详细使用方法）_【星星之火】的博客-程序员秘密

欢迎扫码关注微信公众号：柒零玖嵌入式，更多嵌入式软硬件相关分享！硬件平台：自制imx6ul（详见http://blog.csdn.net/fengyuwuzu0519/article/details/79133851）系统：linux-4.1.15文件系统：busybox-1.22.1.tar.bz2编译器：gcc version 4.9.1 20140710 (prerelease) (cro...............