bzoj1503--treap

时间:2023-03-08 17:05:16

这道题和一般的题目不同,A和S操作要修改所有节点。所以定义基准d,每个节点的工资是它的值+d,这样就能完成所有操作。

I k:将值为k-d的节点插入treap

A k:将d加上k

S k:将d减去k,并将所有值小于min-d的节点删除。

F k:因为treap在插入时就是有序的,所以直接查找。

这里要注意:

在实际编码中,为了减少出错的可能性,一般用一个真实的指针null代替空指针NULL,方法如下:

                            Node *null=new Node();


还有一个略坑的地方就是如果一个员工的初始工资低于工资下界,他将立即离开公司。这不算在离开公司的员工总数内。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
struct Node{
int v,r,s;
Node* ch[];
int cmp(int x)const{
if(x==v)return -;
return x>v?:;
}
void push_up(){
s=ch[]->s+ch[]->s+;
}
};
Node* null=new Node();
Node* root=null;
int i,j,k,n,m,x,y,tot,d,sum;
char c[];
void rotate(Node* &o,int d){
Node* k=o->ch[d^];
o->ch[d^]=k->ch[d];
k->ch[d]=o;
o->push_up();
k->push_up();
o=k;
}
void insert(Node* &o,int x){
if(o==null){
o=new Node();
o->ch[]=o->ch[]=null;
o->v=x;
o->r=rand();
o->s=;
}else{
int d=o->v>x?:;
insert(o->ch[d],x);
if(o->ch[d]->r>o->r)rotate(o,d^);
}
o->push_up();
}
int del(Node* &o,int x){
if(o==null)return ;
if(o->v<x){
int t=o->ch[]->s+;
o=o->ch[];
return t+del(o,x);
}else{
int t=del(o->ch[],x);
o->s-=t;
return t;
}
}
int find(Node* o,int x){
int s=o->ch[]==null?:o->ch[]->s;
if(s+==x)return o->v;
if(s>=x)return find(o->ch[],x);
return find(o->ch[],x-s-);
}
int main()
{
scanf("%d%d",&n,&m);
d=tot=;
for(i=;i<=n;i++){
scanf("%s%d",c,&x);
if(c[]=='I')if(x>=m)insert(root,x-d);
if(c[]=='A')d+=x;else
if(c[]=='S'){
d-=x;
tot+=del(root,m-d);
}else if(c[]=='F')if(x>root->s)printf("-1\n");else printf("%d\n",find(root,x)+d);
}
printf("%d\n",tot);
return ;
}

bzoj1503