招生

Description

 浙江理工大学招生，一开始有0名学生报考，现在有如下几种情况；

1.增加一名报考学生，报考学生成绩为x；

2.一名成绩为x的学生放弃报考。

3.从现在报考的学生来看，老师想知道如果要招生至少x名学生，需要将分数线最高设置为多少；

4.从现在报考的学生来看，如果分数线设置为x，能有几名学生被录取。

第一行先输入一个n，表示有n次操作或查询；

接下来n行，每行输入两个整数opt和x（用空格隔开）：

如果opt为1，则增加一名报考学生，报考学生成绩为x；

如果opt为2，则表示一名成绩为x的学生放弃报考。

如果opt为3，从现在报考的学生来看，老师想知道如果要招生至少x名学生，需要将分数线最高设置为多少，输出最高分数线。

如果opt为4，从现在报考的学生来看，如果分数线设置为x，能有几名学生被录取，输出录取人数。

对于每个输出占一行。

n不超过50000；0<=x<=1000000;1<=k<=现在的学生数。

Input

第一行输入一个n，接下来n行，每行输出两个整数opt，x，用空格隔开

Output

对于每次输出， 输出一个整数占一行

Sample Input

18 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 2 8 3 2 3 3 3 4 3 5 4 8 4 9 4 7

Sample Output

11 10 9 7 4 4 5

HINT

题解：

平衡树Treap直接用

#include<bits/stdc++.h>
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pqueue priority_queue
#define NEW(a,b) memset(a,b,sizeof(a))
const double pi=4.0*atan(1.0);
const double e=exp(1.0);
const int maxn=1e6+8;
typedef long long LL;
typedef unsigned long long ULL;
//typedef pair<LL,LL> P;
const LL mod=1e9+7;
const ULL base=1e7+7;
using namespace std;
struct node{
    int son[2];
    int siz;
    int key,w;
}a[maxn];
int tot=0;
int root=0,vis[maxn];
void up(int i){
    a[i].siz=a[a[i].son[0]].siz+a[a[i].son[1]].siz+1;
}
void Rotate(int &i,int d){
    int t=a[i].son[d];
    a[i].son[d]=a[t].son[!d];
    a[t].son[!d]=i;
    up(i);up(t);
    i=t;
}
void Insert(int &i,int key){
    if(i==0){
        i=++tot;
        a[i].siz=1;a[i].key=key;a[i].w=rand();
        return ;
    }
    a[i].siz++;
    if(a[i].key>=key) {
        Insert(a[i].son[0],key);
        if(a[a[i].son[0]].w<a[i].w) Rotate(i,0);
    }
    else{
        Insert(a[i].son[1],key);
        if(a[a[i].son[1]].w<a[i].w) Rotate(i,1);
    }
}
void Del(int &i,int key){
    if(a[i].key==key){
        if(a[i].son[0]*a[i].son[1]==0)  {i=a[i].son[0]+a[i].son[1];return ;}
        if(a[a[i].son[0]].w>a[a[i].son[1]].w){
            Rotate(i,1);
            Del(a[i].son[0],key);
        }
        else{
            Rotate(i,0);
            Del(a[i].son[1],key);
        }
    }
    else if(a[i].key>key){
        Del(a[i].son[0],key);
    }
    else{
        Del(a[i].son[1],key);
    }
    up(i);
}
int Find(int i,int key){
    if(i==0) return 1;
    if(a[i].key>=key) return Find(a[i].son[0],key);
    else return a[a[i].son[0]].siz+Find(a[i].son[1],key)+1;
}
int Search(int i,int rak){
    if(a[a[i].son[0]].siz==rak-1) return a[i].key;
    if(a[a[i].son[0]].siz>=rak) return Search(a[i].son[0],rak);
    else  return Search(a[i].son[1],rak-a[a[i].son[0]].siz-1);
}
int pre(int i,int key){
    if(i==0) return -10000008;
    if(a[i].key<key) return max(a[i].key,pre(a[i].son[1],key));
    return pre(a[i].son[0],key);
}
int bhe(int i,int key){
    if(i==0) return 10000008;
    if(a[i].key>key) return min(a[i].key,bhe(a[i].son[0],key));
    return bhe(a[i].son[1],key);
}
int main(){
    int n;
    freopen("data1.in","r",stdin);
    freopen("data1.out","w",stdout);
    scanf("%d",&n);
    int opt,x;
    int sum=0;
    while(n--){
        scanf("%d%d",&opt,&x);
        if(opt==1){
            Insert(root,x);
            sum++;
            vis[x]++;
        }
        if(opt==2){
            if(vis[x]){
                Del(root,x);
                sum--;
                vis[x]--;
            }
        }
        if(opt==3){
            printf("%d\n",Search(root,sum-x+1));
        }
        if(opt==4){
            printf("%d\n",sum-Find(root,x)+1);
        }
    }
}