很神奇的一道题，可以用线段树搞，为了练习treap所以拿treap写了。
其实根据询问，删除那个标号就加入平衡树，然后找到最大的和最小的就好了。
一些很烦人的小细节。
//POJ 2892
//by Cydiater
//2016.9.1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
;
const int oo=0x3f3f3f3f;
inline int read(){
,f=;
;ch=getchar();}
+ch-';ch=getchar();}
return x*f;
}
,root=,destory_list[MAXN],top=,last_add,maxx,minn;
char op;
bool vis[MAXN];
struct node{
int leftt,rightt,v,rnd,siz,cnt;
}t[MAXN];
namespace solution{
void updata(int k){
t[k].siz=t[t[k].leftt].siz+t[t[k].rightt].siz+t[k].cnt;
}
void lefturn(int &k){
int tt=t[k].rightt;t[k].rightt=t[tt].leftt;t[tt].leftt=k;
t[tt].siz=t[k].siz;updata(k);k=tt;
}
void righturn(int &k){
int tt=t[k].leftt;t[k].leftt=t[tt].rightt;t[tt].rightt=k;
t[tt].siz=t[k].siz;updata(k);k=tt;
}
void insert(int &k,int x){
){
k=++tol;t[k].leftt=t[k].rightt=;
t[k].siz=;t[k].v=x;t[k].cnt=;
t[k].rnd=rand();
return;
}
t[k].siz++;
if(x==t[k].v)t[k].cnt++;
else if(x>t[k].v){
insert(t[k].rightt,x);
if(t[t[k].rightt].rnd<t[k].rnd)lefturn(k);
}else if(x<t[k].v){
insert(t[k].leftt,x);
if(t[t[k].leftt].rnd<t[k].rnd)righturn(k);
}
}
void del(int &k,int x){
) return;
if(x==t[k].v){
){t[k].cnt--;return;}
)k=t[k].leftt+t[k].rightt;
else if(t[t[k].leftt].rnd<t[t[k].rightt].rnd){
righturn(k);
del(k,x);
}else if(t[t[k].leftt].rnd>t[t[k].rightt].rnd){
lefturn(k);
del(k,x);
}
}else if(x<t[k].v){
t[k].siz--;
del(t[k].leftt,x);
}else if(x>t[k].v){
t[k].siz--;
del(t[k].rightt,x);
}
}
void query_delta(int k,int x){
)return;
if(t[k].v>=x&&t[k].v<maxx)maxx=t[k].v;
if(t[k].v<=x&&t[k].v>minn)minn=t[k].v;
if(x>t[k].v)query_delta(t[k].rightt,x);
else query_delta(t[k].leftt,x);
}
void slove(){
N=read();M=read();
memset(vis,,sizeof(vis));
while(M--){
scanf("%c",&op);
if(op=='R'){
)continue;
last_add=destory_list[top--];
del(root,last_add);
scanf("\n");
continue;
}
num=read();
if(op=='D'){insert(root,num);destory_list[++top]=num;}
if(op=='Q'){
maxx=N+;minn=;
query_delta(root,num);
");
);
}
}
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
slove();
;
}