社区讨论
样例过,但全wa
P1486[NOI2004] 郁闷的出纳员参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @lo2pieb2
- 此快照首次捕获于
- 2023/10/23 17:40 2 年前
- 此快照最后确认于
- 2023/10/23 17:40 2 年前
CPP
#include<bits/stdc++.h>
#define N 300010
const int INF=2e9;
using namespace std;
//#define getchar() (strto1==strto2&&(strto2=(strto1=fsr)+fread(fsr,1,1<<15,stdin),strto1==strto2)?EOF:*strto1++)
//char fsr[1<<15],*strto1=fsr,*strto2=fsr;
inline int read()
{
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s*w;
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
int n,m;
struct Balance_Splay_tree
{
struct node
{
int s[2];
int size,p,v;
void init(int _,int __)
{
v=_,p=__,size=1;
}
}tree[N];
int root,idx,delta,ans;
void pushup(int x)
{
tree[x].size=tree[tree[x].s[0]].size+tree[tree[x].s[1]].size+1;
}
void rotate(int x)
{
int y=tree[x].p,z=tree[y].p;
int k=(tree[y].s[1]==x);
tree[x].p=z,tree[z].s[tree[z].s[1]==y]=x;
tree[y].s[k]=tree[x].s[k^1],tree[tree[x].s[k^1]].p=y;
tree[y].p=x,tree[x].s[k^1]=y;
pushup(y);
pushup(x);
}
void splay(int x,int k)
{
while(tree[x].p!=k)
{
int y=tree[x].p,z=tree[y].p;
if(z!=k)
{
if((tree[z].s[1]==y)^(tree[y].s[1]==x))rotate(x);
else rotate(y);
}
rotate(x);
}
if(k==0)root=x;
}
int insert(int v)
{
int fa=root,p=0;
while(fa)p=fa,fa=tree[fa].s[tree[fa].v<v];
idx++;
fa=idx;
tree[fa].init(v,p);
if(p)tree[p].s[tree[p].v<v]=fa,tree[fa].p=p;
splay(fa,0);
return fa;
}
int Kth(int k)
{
int fa=root;
while(fa)
{
if(tree[tree[fa].s[0]].size+1==k)return tree[fa].v;
else if(tree[tree[fa].s[0]].size+1<k)k-=tree[tree[fa].s[0]].size+1,fa=tree[fa].s[1];
else fa=tree[fa].s[0];
}
}
int get(int k)
{
int fa=root,ans;
while(fa)
{
if(k<=tree[fa].v)ans=fa,fa=tree[fa].s[0];
else fa=tree[fa].s[1];
}
return ans;
}
}Tree;
signed main()
{
n=read(),m=read();
int L=Tree.insert(-INF),R=Tree.insert(INF);
while(n--)
{
char op=getchar();int x=read();
if(op=='I')if(x>=m)Tree.ans++,Tree.insert(x-Tree.delta);
if(op=='A')Tree.delta+=x;
if(op=='S')
{
Tree.delta-=x;
R=Tree.get(m-Tree.delta);
Tree.splay(R,0);
Tree.splay(L,R);
Tree.tree[L].s[1]=0;
Tree.pushup(L),Tree.pushup(R);
}
if(op=='F')
{
if(Tree.tree[Tree.root].size-2<x)write(-1),puts("");
else write(Tree.Kth(Tree.tree[Tree.root].size-x)+Tree.delta),puts("");
}
}
write(Tree.ans-Tree.tree[Tree.root].size+2),puts("");
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...