[BZOJ1503] [NOI 2004] 답답한 출납원, Splay, 나 혼자 안 좋게 조정했어.
코드 주의: 지연 표시는 전역 변수를 켜는 것이 쓰기 쉽습니다. 노드마다dd를 추가한 다음pushdown을 추가할 필요가 없습니다.
없어,하나도 어렵지 않아,제목 뜻 알면 바로 ACTOT.
붙인 코드가 좀 메스꺼워서 많은 함수들이 쓸모가 없고 작은 템플릿 같은 느낌이 든다.(주석이 떨어진del 함수는 틀렸다.)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 1000005
#define inf 0x7fffffff
#define LL long long
#define is(x) (son[fa[x]][1]==x)
using namespace std;
/*
int digit[N];
*/
int ans,flag;
struct node
{
int root,n,top,limit;
int val[N],fa[N],son[N][2],size[N],num[N],snum[N];
// int add[N],num[N];
// long long sum[N],snum[N];
inline void pushup(int x)
{
//size[x]=size[son[x][0]]+size[son[x][1]]+1;
//sum[x]=sum[son[x][0]]+sum[son[x][1]]+val[x]*num[x];
snum[x]=snum[son[x][0]]+snum[son[x][1]]+num[x];
}
/* inline void pushdown(int x)
{
if(add[x])
{
sum[x]+=snum[x]*add[x];
val[x]+=add[x];
add[son[x][0]]+=add[x];
add[son[x][1]]+=add[x];
add[x]=0;
}
}
inline void Build(int l,int r,int mid)
{
if(l<mid)
{
int lmid=l+mid-1>>1;
Build(l,mid-1,lmid);
fa[lmid]=mid;
son[mid][0]=lmid;
}
if(mid<r)
{
int rmid=mid+1+r>>1;
Build(mid+1,r,rmid);
fa[rmid]=mid;
son[mid][1]=rmid;
}
val[mid]=digit[mid],pushup(mid);
}
*/ inline void link(int x,int y,int d){son[y][d]=x;fa[x]=y;}
inline void Rotate(int x)
{
int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
if(t)fa[t]=y;son[y][id]=t;
link(x,z,is(y));
link(y,x,!id);
pushup(y);
}
inline void Splay(int x,int k=0)
{
int y,z;
while(fa[x]!=k)
{
y=fa[x];
z=fa[y];
if(z==k){Rotate(x);break;}
if(is(x)==is(y))Rotate(y),Rotate(x);
else Rotate(x),Rotate(x);
}
pushup(x);
if(!k)root=x;
}
inline int getmin()
{
int x=root;
while(son[x][0])x=son[x][0];
return val[x];
}
inline int getmax()
{
int x=root;
while(son[x][1])x=son[x][1];
Splay(x);
return val[x];
}
inline void findpred(int w)
{
int x=root;
while(son[x][w>val[x]])
{
if(w==val[x])break;
x=son[x][w>val[x]];
}
if(val[x]<w)Splay(root);
else Splay(x);
}
inline bool find(int w,int k=0)
{
if(!n||getmax()<w||getmin()>w)return 0;
int x=root;
while(son[x][w>val[x]])
{
if(val[x]==w){Splay(x,k);return 1;}
x=son[x][w>val[x]];
}
Splay(x,k);
if(val[x]==w)return 1;
return 0;
}
inline int Select(int rank,int k=0)
{/* rank ， k */
if(rank<=0||snum[root]<rank)return -1;
int x=root;
while(!(snum[son[x][0]]<rank&&rank<=snum[son[x][0]]+num[x]))
{
if(snum[son[x][0]]+1>rank)x=son[x][0];
else rank=rank-snum[son[x][0]]-num[x],x=son[x][1];
}
Splay(x,k);
return val[x];
}
inline void newnode(int &x,int y,int w)
{
x=++top;n++;
son[x][0]=son[x][1]=0;
val[x]=w;
fa[x]=y;
snum[x]=num[x]=size[x]=1;
}
void insert(int w,int k=0)
{
int x=root;
while(son[x][w>val[x]])
{
if(w==val[x])
{
n++;
num[x]++;
snum[x]++;
Splay(x,k);
return ;
}
x=son[x][w>val[x]];
}
newnode(son[x][w>val[x]],x,w);
Splay(son[x][w>val[x]]);
}
inline void del(int x,int y)
{
if(!x)return ;
if(val[x]>=limit)del(son[x][0],x),pushup(x);
else {
int t=snum[son[x][0]]+num[x];
ans+=t;n-=t;
link(son[x][1],y,0);
del(son[x][1],y);
}
}
/* void del(int x,int y)
{
if(!x)return ;
if(val[x]<limit)
{
ans+=snum[son[x][0]]+num[x];
link(son[x][1],y,0);
del(son[x][1],y);
}
else del(son[x][0],x);
pushup(y);
}
inline void Insert(int x,int p)
{// ，x （ ）
int l=Select(x,0),r=Select(x+1,l);
newnode(son[r][0],r,p);
Splay(n,0);
}
inline void ChangeS(int x,int p){x=Select(x,0),val[x]=p,Splay(x);}// x p
*/
}tree;
void handle()
{
int i,j,k;
int n,m;
char a[5];
scanf("%d%d",&n,&tree.limit);
tree.newnode(tree.root,0,inf);
for(i=1;i<=n;i++)
{
scanf("%s%d",a,&k);
if(a[0]=='I'){
if(k<tree.limit+flag);//ans++;
else tree.insert(k-flag);
}
else if(a[0]=='A'){
flag+=k;
tree.limit-=k;
}
else if(a[0]=='S'){
flag-=k;
tree.limit+=k;
tree.getmax();
tree.del(tree.root,0);
}
else
{
j=tree.Select(tree.n-k);
if(j==-1)puts("-1");
else printf("%d
",j+flag);
}
}
printf("%d
",ans);
}
int main()
{
handle();
return 0;
}
Google 번역으로 복사
번역 결과
좋은 웹페이지 즐겨찾기
