原题地址:https://www.luogu.org/problemnew/show/P1486
题目简述
一个序列a，初始为空。
随时插入一个数，查询第k大，全体加，全体减。
但是如果任何数在任何时刻低于给定的下界MIN，则立即移除出序列。
思路
插入，查询第k大，容易发现是BST题。于是上Treap。
全体加全体减暴力加肯定不行，考虑用变量delta储存变化情况。全体加n就是delta+=n（n为负就是减）
于是每个数实际的值是：树里储存该数的值+delta ——①
减了之后可能会有数低于下界，查找最小的数判断是不是小于MIN，是的话删除，重复直到不再小于MIN。
注意新插入的数不应该受之前的加减影响，所以将一个数字num插入树中时，如果直接把num插入树中，就变成num+delta了。
实际应该插入的是num-delta，这样结合上文①，现在这个数实际的值就是num本身了。
提供一个指针实现的Treap，不推荐使用其实，调的时候快把我搞吐血。
代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <cctype>
using namespace std;
const int MAXN=200010;
struct Node
{
int d,rnd,size;
Node *ch[2],*pa;
}pool[MAXN],*root;
int tot=0;
Node *newnode(int d)
{
Node *p=&pool[++tot];
p->d=d;p->rnd=rand();p->size=1;
p->ch[0]=p->ch[1]=NULL;
return p;
}
inline int size(Node *p)
{
return p?p->size:0;
}
void update(Node *p)
{
p->size=size(p->ch[0])+size(p->ch[1])+1;
}
void rotate(Node *p,int t)
{
Node *pa=p->pa,*gp=pa->pa,*son=p->ch[t^1];
pa->ch[t]=son;
if(son)son->pa=pa;
if(gp)gp->ch[pa==gp->ch[1]]=p;
p->pa=gp;
p->ch[t^1]=pa;
pa->pa=p;
if(pa==root)root=p;
update(pa);
update(p);
}
void treap(Node *p)
{
while(true)
{
if(p==root || p->rnd >= p->pa->rnd)break;
rotate(p,p==p->pa->ch[1]);
}
}
void insert(Node *r,Node *p)
{
if(!r)
{
root=p;
return;
}
int f=(p->d >= r->d);
if(!r->ch[f])
{
r->ch[f]=p;
p->pa=r;
}
else
insert(r->ch[f],p);
update(r);
}
Node* find(Node *r,int x)
{
if(x<=size(r->ch[0]))return find(r->ch[0],x);
if(x==size(r->ch[0])+1)return r;
return find(r->ch[1],x-size(r->ch[0])-1);
}
void del(Node *p)
{
if(!p->ch[0] && !p->ch[1])
{
if(p==root)
{
root=NULL;
return;
}
Node *pa=p->pa;
if(pa)
pa->ch[p==pa->ch[1]]=NULL;
while(p!=root)
update(p=p->pa);
return;
}
if(p->ch[0] && p->ch[1])
{
int f=(p->ch[1]->rnd < p->ch[0]->rnd);
rotate(p->ch[f],f);
}
else
{
int f=1;
if(p->ch[0])f=0;
rotate(p->ch[f],f);
}
del(p);
}
int kth(Node *r,int x)
{
if(x<=size(r->ch[0]))return kth(r->ch[0],x);
if(x==size(r->ch[0])+1)return r->d;
return kth(r->ch[1],x-size(r->ch[0])-1);
}
char getUpper()
{
char c;
while(c=getchar())
if(isupper(c))
return c;
}
int main()
{
srand((int)time(NULL));
int Q,Min,x;
char op;
scanf("%d%d",&Q,&Min);
int ans=0,delta=0;
while(Q--)
{
op=getUpper();
scanf("%d",&x);
switch(op)
{
case 'I':
{
if(x<Min)break;
Node *p=newnode(x-delta);
insert(root,p);
treap(p);
break;
}
case 'A':
delta+=x;
break;
case 'S':
{
delta-=x;
int xtq=size(root);
for(int i=1;i<=xtq;i++)
if(kth(root,1)+delta<Min)
{
del(find(root,1));
ans++;
}
else break;
break;
}
case 'F':
if(x>size(root))printf("-1
");
else printf("%d
",kth(root,size(root)-x+1)+delta);
break;
}
}
printf("%d
",ans);
return 0;
}