题目链接
思路
这个题其实就是对于treap中的删除操作进行一些修改。自己yy了一种做法。就是在删除的时候，如果要删除的数比这棵子树的根大，那么就把根变成根的右孩子，这样就相当于删除了整棵左子树和根节点。然后重新维护一下siz，并且维护一下平衡性就行了。
竟然把rotate函数写错了。调了30min。又没正确理解
如果某个员工的初始工资低于最低工资标准,那么将不计入最后的答案内
这句话的含义，又调了30min。23333
代码
//每次修改操作之后都进行一次删除，并且更改删除函数
/*
* @Author: wxyww
* @Date: 2018-12-02 08:41:38
* @Last Modified time: 2018-12-02 10:02:49
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
#define ls TR[cur].ch[0]
#define rs TR[cur].ch[1]
typedef long long ll;
const int N = 100000 + 100,INF = 1e9 + 7;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node {
int ch[2],id,val,siz,cnt;
}TR[N];
int MIN;
void up(int cur) {
TR[cur].siz = TR[ls].siz + TR[rs].siz + TR[cur].cnt;
}
void rotate(int &cur,int f) {
int son = TR[cur].ch[f];
TR[cur].ch[f] = TR[son].ch[f ^ 1];
TR[son].ch[f ^ 1] = cur;
up(cur);
cur = son;
up(cur);
}
int tot;
void insert(int &cur,int val) {
if(!cur) {
cur = ++tot;
TR[cur].id = rand();
TR[cur].val = val;
TR[cur].siz = TR[cur].cnt = 1;
return;
}
TR[cur].siz++;
if(val == TR[cur].val) {TR[cur].cnt++;return;}
int d = val > TR[cur].val;
insert(TR[cur].ch[d],val);
if(TR[TR[cur].ch[d]].id < TR[cur].id) rotate(cur,d);
}
void del(int &cur,int val) {
if(!cur) return;
if(val <= TR[cur].val) del(ls,val);
else {
del(rs,val);
cur = rs;
}
up(cur);
if(TR[ls].id < TR[cur].id && ls) rotate(cur,0);
if(TR[rs].id < TR[cur].id && rs) rotate(cur,1);
}
int kth(int cur,int now) {
while(1) {
if(now > TR[rs].siz + TR[cur].cnt) now -= TR[rs].siz + TR[cur].cnt,cur = ls;
else if(now <= TR[rs].siz) cur = rs;
else return TR[cur].val;
}
}
int main() {
int rt = 0;
int n = read(),change = 0,num = 0;
MIN = read();
char c;
while(n--) {
int x;
scanf("\n%c %d",&c,&x);
if(c == 'I') {
x -= change;
if(x >= MIN) num++,insert(rt,x);
}
if(c == 'A') MIN -= x,change += x;
if(c == 'S') {
MIN += x;
del(rt,MIN);
change -= x;
}
if(c == 'F') {
if(x > TR[rt].siz) puts("-1");
else printf("%d\n",kth(rt,x) + change);
}
}
cout<<num - TR[rt].siz<<endl;
return 0;
}