Description
设计数据结构支持:
1 x 若x不存在,插入x
2 x 若x存在,删除x
3 输出当前最小值,若不存在输出-1
4 输出当前最大值,若不存在输出-1
5 x 输出x的前驱,若不存在输出-1
6 x 输出x的后继,若不存在输出-1
7 x 若x存在,输出1,否则输出-1
Input
第一行给出n,m 表示出现数的范围和操作个数
接下来m行给出操作
n<=10^6,m<=2*10^6,0<=x<n
Output
Sample Input
10 11
1 1
1 2
1 3
7 1
7 4
2 1
3
2 3
4
5 3
6 2
Sample Output
1
-1
2
2
2
-1
题目分析
一看这不是treap裸题？ 码了一发T了 原来这题卡treap=.=
尽管时间吃紧 但全是set裸操作嘛 +一个fread读入优化就过了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
set<int>s;
set<int>::iterator it;
int n,m;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int int_read(){
char ch=nc();int sum=0;
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum;
}
int main()
{
n=int_read(),m=int_read();
for(int i=1;i<=m;i++)
{
int tmp,x;
tmp=int_read();
if(tmp==1) x=int_read(),s.insert(x);
else if(tmp==2) x=int_read(),s.erase(x);
else if(tmp==3) printf("%d\n",s.size()?*s.begin():-1);
else if(tmp==4) printf("%d\n",s.size()?*--s.end():-1);
else if(tmp==5) x=int_read(),it=s.lower_bound(x),printf("%d\n",it!=s.begin()?*--it:-1);
else if(tmp==6) x=int_read(),it=s.upper_bound(x),printf("%d\n",it!=s.end()?*it:-1);
else if(tmp==7) x=int_read(),printf("%d\n",s.count(x)?1:-1);
}
return 0;
}
