社区讨论

为什么只有20

P1486[NOI2004] 郁闷的出纳员参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mi7dds4a
此快照首次捕获于
2025/11/20 19:50
4 个月前
此快照最后确认于
2025/11/20 19:50
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct BST{
    int data;
    int fa,l,r,num,ln,rn;
}tree[100005];
int n,root=0,tot=0,ans=0,tttot=0,minn,dlt=0;
void Zag(int x){
    int y=tree[x].fa;
    tree[y].r=tree[x].l;
    if(tree[x].l)tree[tree[x].l].fa=y;
    tree[x].fa=tree[y].fa;
    if(tree[y].fa){
        if(y==tree[tree[y].fa].l)tree[tree[y].fa].l=x;
        else tree[tree[y].fa].r=x;
    }
    tree[x].l=y;
    tree[y].fa=x;
    tree[y].rn=tree[x].ln;
    tree[x].ln=tree[y].ln+tree[y].rn+tree[y].num;
}
void Zig(int x){
    int y=tree[x].fa;
    tree[y].l=tree[x].r;
    if(tree[x].r)tree[tree[x].r].fa=y;
    tree[x].fa=tree[y].fa;
    if(tree[y].fa){
        if(y==tree[tree[y].fa].l)tree[tree[y].fa].l=x;
        else tree[tree[y].fa].r=x;
    }
    tree[x].r=y;
    tree[y].fa=x;
    tree[y].ln=tree[x].rn;
    tree[x].rn=tree[y].ln+tree[y].rn+tree[y].num;
}
void Splay(int x){
    int p;
    while(tree[x].fa){
        p=tree[x].fa;
        if(!tree[p].fa){
            if(x==tree[p].l)Zig(x);
            else Zag(x);
            break;
        }
        if(x==tree[p].l){
            if(p==tree[tree[p].fa].l){
                Zig(p);
                Zig(x);
            }
            else {
                Zig(x);
                Zag(x);
            }
        }
        else {
            if(p==tree[tree[p].fa].r){
                Zag(p);
                Zag(x);
            }
            else {
                Zag(x);
                Zig(x);
            }
        }
    }
    root=x;
}
bool Find_Data(int x){
    int p=root;
    while(p){
        if(x==tree[p].data){
            return Splay(p),1;
        }
        if(x<tree[p].data)p=tree[p].l;
        else p=tree[p].r;
    }
    return 0;
}
int Find_Rank(int k){
    int p=root;
    if(k>tttot)return -1;
    while(1){
        //cout<<tree[p].data<<' '<<tree[p].ln<<' '<<tree[p].num<<endl;
        if(tree[p].rn<k&&(tree[p].rn+tree[p].num>=k))return tree[p].data;
        if(tree[p].rn>=k)p=tree[p].r;
        else {
            k=k-tree[p].rn-tree[p].num;
            p=tree[p].l;
        }
    }
}
void Insert(int x){
    int p=root,f;
    while(p){
        f=p;
        if(tree[p].data==x){
            tree[p].num++;
            tttot++;
            return ;
        }
        if(x<tree[p].data){
            tree[p].ln++;
            p=tree[p].l;
        }
        else {
            tree[p].rn++;
            p=tree[p].r;
        }
    }
    tot++;
    tttot++;
    tree[tot].data=x;
    tree[tot].num=1;
    if(!root){
        root=tot;
        return ;
    }
    tree[tot].fa=f;
    if(x<=tree[f].data)tree[f].l=tot;
    else tree[f].r=tot;
    Splay(tot);
}
void Delete(int x){
    if(!Find_Data(x))return ;
    int p=root;
    if(tree[p].num>1){
        tree[p].num--;
        return ;
    }
    int ls=tree[p].l,rs=tree[p].r;
    if(!ls&&!rs){
        root=0;
        return ;
    }
    if(!ls){
        root=rs;
        tree[rs].fa=0;
        return ;
    }
    if(!rs){
        root=ls;
        tree[ls].fa=0;
        return ;
    }
    p=ls;
    tree[ls].fa=0;
    while(tree[p].r)p=tree[p].r;
    Splay(p);
    tree[p].r=rs,tree[rs].fa=p;
    tree[p].rn=tree[rs].ln+tree[rs].rn+tree[rs].num;
}
int Pred(int x){
    int p=root,res=-0x3f3f3f3f;
    while(p){
        //cout<<tree[p].data<<endl;
        if(tree[p].data<x&&tree[p].data>res)res=tree[p].data;
        if(x<=tree[p].data)p=tree[p].l;
        else p=tree[p].r;
    }
    return res;
}
int Succ(int x){
    int p=root,res=0x3f3f3f3f;
    while(p){
        if(tree[p].data>x&&tree[p].data<res)res=tree[p].data;
        if(x<tree[p].data)p=tree[p].l;
        else p=tree[p].r;
    }
    return res;
}
int main(){
    scanf("%d%d",&n,&minn);
    for(int i=1;i<=n;i++){
    	char ch;
    	int x;
    	cin>>ch>>x;
    	if(ch=='I'){
    		if(minn<=x)Insert(x-dlt);
            else ans++;
    	}
    	if(ch=='A')dlt+=x;
    	if(ch=='S'){
    		dlt-=x;
    		if(Pred(minn-dlt)==-0x3f3f3f3f)continue;
    		Find_Data(Pred(minn-dlt));
    		ans+=tree[root].ln+tree[root].num;
    		tttot-=tree[root].ln+tree[root].num;
    		tree[root].l=tree[root].ln=0;
    		Delete(tree[root].data);
    	}
    	if(ch=='F')printf("%d\n",Find_Rank(x)==-1?-1:Find_Rank(x)+dlt);
    }
    printf("%d\n",ans);
    return 0;
}
//813013988

回复

1 条回复,欢迎继续交流。

正在加载回复...