P1486 [NOI2004] 郁闷的出纳员
题目翻译:
维护一个可重数集,共有 \(n\) 次操作,和一个最小限制 \(min\),共有四种操作:
- \(I\) \(k\) 给集合添加 \(k\) 若 \(k<min\) 则直接删除(不算入删除个数)
- \(A\) \(k\) 将集合中的所有元素加上 \(k\)
- \(S\) \(k\) 将所有元素减少 \(k\) 并将所有值小于 \(min\) 的删除
- \(F\) \(k\) 输出集合中元素从大到小的第 \(k\) 名的值,若 \(k\) 大于当前元素的值,则输出 \(-1\)
最后还要输出总共删除了多少元素
思路:
对于求第 \(k\) 大的数和随时可以插入等操作,很容易想到用平衡树来维护。由于可能会有重复的数,我们可以给每个节点都维护一个 \(cnt\) 用来储存该节点数的个数。
- 对于插入操作就与普通的插入没有区别,只要特判一下,看是否有一样的,有就直接给该节点加一。并且要特判一下是否小于 \(min\),若小于则直接跳过。
void ins(int key){
if(key<mi)return;
int now=rt,f=0;
while(now && tr[now].key!=key){
f=now;
now=tr[now].s[key>tr[now].key];
}
if(now){
tr[now].cnt++;
splay(now);
return;
}
now=newnode(key);
fa(now)=f;
if(f)tr[f].s[key>tr[f].key]=now;
splay(now);
}
- 对于给所有加上 \(k\)我们可以暴力的给所有节点都加上 \(k\),不管是否已经删除或者有没有用,应为删除的节点已经没有与树有连边,所以无法访问,自然没有影响,时间复杂度为 \(O(n)\)
for(int i=1;i<=idx;i++){
tr[i].key+=k;
}
- 对于对所有节点减去 \(k\),我们也可以全部减去,但为了删点,我们可以先找到最接近且 \(\geq k+min\) 的点,将他给 \(splay\) 到根节点,这样所有减去 \(k\) 会小于 \(min\) 的节点都会在根节点的左子树,这样只需要给 \(ans\) 加上子树大小,然后断开连接即可。最后给所有节点减去 \(k\).
void find(int key){
int now=rt;
while(key!=tr[now].key && tr[now].s[key>tr[now].key]){
now=tr[now].s[key>tr[now].key];
}
splay(now);
}
int nxt(int key){
find(key);
if(tr[rt].key>=key)return rt;
int now=rc(rt);
while(lc(now))now=lc(now);
return now;
}
void del2(int x){
int now=nxt(x+mi);
splay(now);
ans+=tr[lc(now)].siz;
lc(now)=0;
pushup(now);
for(int i=1;i<=idx;i++){
tr[i].key-=x;
}
}
- 查找第 \(k\) 大的数。与普通查找没有什么区别但要注意的是,由于为了防止树中没有符合要求的节点,所以会先加入一个极大值,所以找的时候要找第 \(k+1\) 大的数。其次,由于有重复的数,所以在转移时还会要算上 \(cnt\)值
int kth(int rk){
int now=rt;
if(rk>=tr[now].siz)return -1;
rk++;
while(true){
int sz=tr[rc(now)].siz;
if(sz>=rk && rc(now)){
now=rc(now);
}
else if(rk>tr[rc(now)].siz+tr[now].cnt){
rk-=sz+tr[now].cnt;
now=lc(now);
}
else{
return tr[now].key;
}
}
}
完整代码:
#include<bits/stdc++.h>
#define lc(x) tr[(x)].s[0]
#define rc(x) tr[(x)].s[1]
#define fa(x) tr[(x)].fa
using namespace std;
const int N=3e5+10;
struct tree{
int s[2],fa,siz,key,cnt;
tree(){s[0]=s[1]=fa=siz=cnt=key=0;}
}tr[N];
int idx,rt,mi,ans;
void pushup(int x){
tr[x].siz=tr[lc(x)].siz+tr[rc(x)].siz+tr[x].cnt;
}
void clear(int x){
lc(x)=rc(x)=fa(x)=tr[x].siz=tr[x].key=tr[x].cnt=0;
}
int newnode(int key){
tr[++idx].key=key;
tr[idx].siz=1;
tr[idx].cnt=1;
return idx;
}
int get(int x){
return x==rc(fa(x));
}
void rotate(int x){
int y=fa(x),z=fa(y),c=get(x);
if(tr[x].s[c^1])fa(tr[x].s[c^1])=y;
tr[y].s[c]=tr[x].s[c^1];
tr[x].s[c^1]=y;
fa(y)=x;
fa(x)=z;
if(z)tr[z].s[y==rc(z)]=x;
pushup(y);
pushup(x);
}
void splay(int x){
for(int f=fa(x);f=fa(x),f;rotate(x)){
if(fa(f))rotate(get(x)==get(f)?f:x);
}
rt=x;
}
void ins(int key){
if(key<mi)return;
int now=rt,f=0;
while(now && tr[now].key!=key){
f=now;
now=tr[now].s[key>tr[now].key];
}
if(now){
tr[now].cnt++;
splay(now);
return;
}
now=newnode(key);
fa(now)=f;
if(f)tr[f].s[key>tr[f].key]=now;
splay(now);
}
int kth(int rk){
int now=rt;
if(rk>=tr[now].siz)return -1;
rk++;
while(true){
int sz=tr[rc(now)].siz;
if(sz>=rk && rc(now)){
now=rc(now);
}
else if(rk>tr[rc(now)].siz+tr[now].cnt){
rk-=sz+tr[now].cnt;
now=lc(now);
}
else{
return tr[now].key;
}
}
}
void find(int key){
int now=rt;
while(key!=tr[now].key && tr[now].s[key>tr[now].key]){
now=tr[now].s[key>tr[now].key];
}
splay(now);
}
int nxt(int key){
find(key);
if(tr[rt].key>=key)return rt;
int now=rc(rt);
while(lc(now))now=lc(now);
return now;
}
void del2(int x){
int now=nxt(x+mi);
splay(now);
ans+=tr[lc(now)].siz;
lc(now)=0;
pushup(now);
for(int i=1;i<=idx;i++){
tr[i].key-=x;
}
}
int main(){
int n;
scanf("%d%d",&n,&mi);
ins(1547483647);
for(int i=1;i<=n;i++){
char op;
int k;
cin>>op>>k;
if(op=='I'){
ins(k);
}
if(op=='A'){
for(int i=1;i<=idx;i++){
tr[i].key+=k;
}
}
if(op=='S'){
del2(k);
}
if(op=='F'){
printf("%d\n",kth(k));
}
}
printf("%d\n",ans);
}