【BZOJ1503】【NOI2004】郁闷的出纳员

一道平衡树裸题。。

codevs过了 BZOJ显示RE。。郁闷的oier

我已经对每道题都判我RE的BZOJ绝望了

管他的反正codevs上A了 233

// <1503.cpp> - 01/30/16 22:23:31
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
const int INF=1000000000;
const int MAXN=110001;
int root,tot,mn,ans,flag;
int val[MAXN],size[MAXN];
int s[MAXN][2],f[MAXN];
void update(int a){
	int l=s[a][0],r=s[a][1];
	size[a]=size[l]+size[r]+1;
}
void R(int a,int &k){
	int p=f[a],g=f[p];
	bool l=a==s[p][1],r=!l;
	if(p==k)k=a;
	else s[g][s[g][1]==p]=a;f[a]=g;
	f[s[a][r]]=p;s[p][l]=s[a][r];
	f[p]=a;s[a][r]=p;
	update(p);update(a);
}
void splay(int a,int &k){
	while(a!=k){
		int p=f[a];
		if(p!=k){
			if((s[p][0]==a)^(s[f[p]][0]==p))R(a,k);
			else R(p,k);
		}
		R(a,k);
	}
}
void insert(int x){
	if(x+flag<mn)return;
	int a=++tot;
	val[a]=x;size[a]=1;
	if(!root){root=a;return;}
	int now=root;
	while(s[now][val[a]>val[now]])now=s[now][val[a]>val[now]];
	s[now][val[a]>val[now]]=a;f[a]=now;
	splay(a,root);
}
int kill(int x){
	insert(x);
	splay(tot,root);
	int ans=size[s[root][0]];
	root=s[root][1];
	return ans;
}
int src(int now,int k){
	int l=s[now][0],r=s[now][1];
	if(size[r]+1==k)return now;
	if(size[r]>=k)return src(r,k);
	return src(l,k-size[r]-1);
}
int main(){
	int n=getint();mn=getint();
	char s;
	insert(INF);
	while(n--){
		cin>>s;
		if(s=='I')insert(getint()-flag);
		else if(s=='A')flag+=getint();
		else if(s=='S'){flag-=getint();ans+=kill(mn-flag);}
		else{
			int k=getint();
			if(k+1>size[root])cout<<-1<<endl;
			else printf("%d\n",val[src(root,k+1)]+flag);
		}
	}
	cout<<ans;
	return 0;
}

// <1503.cpp> - 01/30/16 22:23:31

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int INF=1000000000;

const int MAXN=110001;

int root,tot,mn,ans,flag;

int val[MAXN],size[MAXN];

int s[MAXN][2],f[MAXN];

void update(int a){

int l=s[a][0],r=s[a][1];

size[a]=size[l]+size[r]+1;

}

void R(int a,int &k){

int p=f[a],g=f[p];

bool l=a==s[p][1],r=!l;

if(p==k)k=a;

else s[g][s[g][1]==p]=a;f[a]=g;

f[s[a][r]]=p;s[p][l]=s[a][r];

f[p]=a;s[a][r]=p;

update(p);update(a);

}

void splay(int a,int &k){

while(a!=k){

int p=f[a];

if(p!=k){

if((s[p][0]==a)^(s[f[p]][0]==p))R(a,k);

else R(p,k);

}

R(a,k);

}

void insert(int x){

if(x+flag<mn)return;

int a=++tot;

val[a]=x;size[a]=1;

if(!root){root=a;return;}

int now=root;

while(s[now][val[a]>val[now]])now=s[now][val[a]>val[now]];

s[now][val[a]>val[now]]=a;f[a]=now;

splay(a,root);

}

int kill(int x){

insert(x);

splay(tot,root);

int ans=size[s[root][0]];

root=s[root][1];

return ans;

}

int src(int now,int k){

int l=s[now][0],r=s[now][1];

if(size[r]+1==k)return now;

if(size[r]>=k)return src(r,k);

return src(l,k-size[r]-1);

}

int main(){

int n=getint();mn=getint();

char s;

insert(INF);

while(n--){

cin>>s;

if(s=='I')insert(getint()-flag);

else if(s=='A')flag+=getint();

else if(s=='S'){flag-=getint();ans+=kill(mn-flag);}

else{

int k=getint();

if(k+1>size[root])cout<<-1<<endl;

else printf("%d\n",val[src(root,k+1)]+flag);

}

cout<<ans;

return 0;

}