社区讨论
为什么只有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 条回复,欢迎继续交流。
正在加载回复...