809
NOI 2004 鬱悶的出納員 Splay
網址：https://www.lydsy.com/JudgeOnline/problem.php?id=1503
所有的操作都比較簡單，而對於調整工資，就必須思考下，不過也簡單，直接變成調整界限，和新來員工工資即可，剩下的就是splay。。。
/**************************************************************
Problem: 1503
User: h6363817
Language: C++
Result: Accepted
Time:992 ms
Memory:3228 kb
****************************************************************/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mm=100020;
const int oo=2e9;
struct SplayTree
{
int son[mm][2],far[mm],val[mm],sum[mm];
int rt,size;
void PushUp(int x)
{
sum[x]=sum[son[x][0]]+sum[son[x][1]]+1;
}
void Link(int x,int y,int c)
{
far[x]=y,son[y][c]=x;
}
void Rotate(int x,int c)
{
int y=far[x];
Link(x,far[y],son[far[y]][1]==y);
Link(son[x][!c],y,c);
Link(y,x,!c);
PushUp(y);
}
void Splay(int x,int g)
{
for(; far[x]!=g;)
{
int y=far[x],cx=(son[y][1]==x),cy=(son[far[y]][1]==y);
if(far[y]==g)Rotate(x,cx);
else
{
if(cx==cy)Rotate(y,cy);
else Rotate(x,cx);
Rotate(x,cy);
}
}
PushUp(x);
if(!g)rt=x;
}
void NewNode(int y,int &x,int a)
{
x=++size;
far[x]=y,val[x]=a,sum[x]=1;
son[x][0]=son[x][1]=0;
}
void Insert(int a)
{
int x=rt;
while(son[x][val[x]<a])x=son[x][val[x]<a];
NewNode(x,son[x][val[x]<a],a);
Splay(size,0);
}
void Prepare()
{
NewNode(size=0,rt,-oo);
NewNode(rt,son[rt][1],oo);
sum[rt]=2;
}
int Suc(int a)
{
int x=rt,ret=oo;
while(x)
{
if(val[x]==a) return a;
if(val[x]>a) ret=min(ret,val[x]);
x=son[x][val[x]<a];
}
return ret;
}
int Pre(int a)
{
int x=rt,ret=-oo;
while(x)
{
if(val[x]==a)return a;
if(val[x]<a)ret=max(ret,val[x]);
x=son[x][val[x]<a];
}
return ret;
}
int Find(int a)
{
int x=rt,ans=0;
while(x)
{
if(val[x]==a) ans=x;
x=son[x][val[x]<a];
}
return ans;
}
int Select(int k,int g)
{
int x=rt;
while(sum[son[x][1]]!=k)
{
if(sum[son[x][1]]>k) x=son[x][1];
else k-=(sum[son[x][1]]+1),x=son[x][0];
}
Splay(x,g);
return val[x];
}
int Delete(int a)
{
int x=Find(a),ans=0;
if(x)
{
Splay(1,0);
Splay(x,1);
ans=sum[son[x][0]];
son[x][0]=0;
Splay(x,0);
}
return ans;
}
} spt;
int main()
{
int n,m,w,a,ans;
char s[5];
while(~scanf("%d%d",&n,&m))
{
spt.Prepare();
w=ans=0;
while(n--)
{
scanf("%s%d",s,&a);
if(s[0]=='I')
{
a-=w;
if(a>=m-w) spt.Insert(a);
}
if(s[0]=='A') w+=a;
if(s[0]=='S') w-=a,ans+=spt.Delete(spt.Suc(m-w));
if(s[0]=='F')
{
if(spt.sum[spt.rt]<a+2) puts("-1");
else printf("%d\n",spt.Select(a,0)+w);
}
}
printf("%d\n",ans);
}
return 0;
}
最後更新：2017-04-03 16:48:56