转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
Splay Tree写了4、5个小时,debug不能,只有跪舔啊。
改用SBT,还是SB Tree好用。。。
把一个变量用作类似线段树中的延迟标记,不需要在每次加或者减的时候进行全部更新。在后来插入的结点中,应该当之前的延迟算进去,如果初始就小于下限的不添加,而且也不算作最后离开的人数。
在删除的时候,如果根结点小于下限,说明左子树以及根结点都小于下限,直接把右子树作为根。对新的树进行处理。
如果根结点大于下限,说明右子树也全部大于下限,对左子树进行处理,最后更新根的size。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
struct SBT{
//左子树指针,右子树指针,大小,键值
int left,right,size,key;
void Init(){
left=right=key=0;
size=1;
}
}T[N];
int root,tot; //根的位置以及节点个数
//左旋转处理
void Left_rot(int &x){
int k=T[x].right;
T[x].right=T[k].left;
T[k].left=x;
T[k].size=T[x].size;
T[x].size=T[T[x].left].size+T[T[x].right].size+1;
x=k;
}
//右旋转处理
void Right_rot(int &x){
int k=T[x].left;
T[x].left=T[k].right;
T[k].right=x;
T[k].size=T[x].size;
T[x].size=T[T[x].left].size+T[T[x].right].size+1;
x=k;
}
//调整处理
void Maintain(int &r,bool flag){
if(flag){ //更新右子树
if(T[T[T[r].right].right].size>T[T[r].left].size)
Left_rot(r);
else if(T[T[T[r].right].left].size>T[T[r].left].size){
Right_rot(T[r].right);
Left_rot(r);
}
else
return;
}
else{ //更新在左子树
if(T[T[T[r].left].left].size>T[T[r].right].size)
Right_rot(r);
else if(T[T[T[r].left].right].size>T[T[r].right].size){
Left_rot(T[r].left);
Right_rot(r);
}
else
return;
}
//更新子树,然后再更新根,直到平衡为止
Maintain(T[r].left,false);
Maintain(T[r].right,true);
Maintain(r,false);
Maintain(r,true);
}
//插入新节点
void Insert(int &r,int k){
if(r==0){
r=++tot;
T[r].Init();
T[r].key=k;
}
else{
T[r].size++;
if(k<T[r].key)
Insert(T[r].left,k);
else
Insert(T[r].right,k);
//插入后要调整,保证平衡
Maintain(r,k>=T[r].key);
}
}
//删除结点,利用的是前驱替换
int Remove(int &r,int k){
int d_key;
if(!r)
return 0;
T[r].size--;
//前者说明就是要删的节点,后两者说明不存在此节点
if(T[r].key==k||(T[r].left==0&&k<T[r].key)||(T[r].right==0&&k>T[r].key)){
d_key=T[r].key;
if(T[r].left&&T[r].right)
T[r].key=Remove(T[r].left,k+1);
else
r=T[r].left+T[r].right;
}
else Remove(k<T[r].key?T[r].left:T[r].right,k);
}
void Delete(int &r,int delay,int min_val){
if(!r) return;
if(T[r].key+delay<min_val) {
r=T[r].right;
Delete(r,delay,min_val);
}
else{
Delete(T[r].left,delay,min_val);
T[r].size=T[T[r].right].size+T[T[r].left].size+1;
}
}
//取得最大值,即一直遍历到最右的结点
int Get_Max(int &r){
while(T[r].right)
r=T[r].right;
return r;
}
//取得最小值,即一直遍历到最左的结点
int Get_Min(int &r){
while(T[r].left)
r=T[r].left;
return r;
}
//获得前驱
int Get_Pre(int &r,int y,int k){
if(r==0) return y;
if(k>T[r].key)
Get_Pre(T[r].right,r,k);
else
Get_Pre(T[r].left,y,k);
}
//获得后继
int Get_Next(int &r,int y,int k){
if(r==0) return y;
if(k<T[r].key)
Get_Next(T[r].left,r,k);
else
Get_Next(T[r].right,y,k);
}
//取得第K小的数,注:暂不能解决有重复数的
int Get_Min_Kth(int &r,int k){
int t=T[T[r].left].size+1;
if(t==k) return T[r].key;
if(t<k) return Get_Min_Kth(T[r].right,k-r);
else return Get_Min_Kth(T[r].left,k);
}
//取得第K大的数
int Get_Max_Kth(int &r,int k){
int t=T[T[r].right].size+1;
if(t==k) return T[r].key;
if(t<k) return Get_Max_Kth(T[r].left,k-t);
else return Get_Max_Kth(T[r].right,k);
}
//获得结点的名次
int Get_Rank(int &r,int k){
if(k<T[r].key)
return Get_Rank(T[r].left,k);
else if(k>T[r].key)
return Get_Rank(T[r].right,k)+T[T[r].left].size+1;
else
return T[T[r].left].size+1;
}
//排序
void Inorder(int &r){
if(r==0) return;
Inorder(T[r].left);
printf("%d\n",T[r].key);
Inorder(T[r].right);
}
int main(){
int q,delay,miv_val;
while(scanf("%d%d",&q,&miv_val)!=EOF){
tot=delay=root=0;
while(q--){
char str[10];
int k;
scanf("%s%d",str,&k);
if(str[0]=='I'){
if(k<miv_val)
continue;
Insert(root,k-delay);
}
else if(str[0]=='A')
delay+=k;
else if(str[0]=='F')
printf("%d\n",T[root].size<k?-1:(Get_Max_Kth(root,k)+delay));
else{
delay-=k;
Delete(root,delay,miv_val);
}
}
printf("%d\n",tot-T[root].size);
}
return 0;
}
分享到:
相关推荐
NOI2004测试数据
NOI题库1.6一些题目,可供初学者参考
NOI大纲NOI大纲NOI大纲.pdf
NOI2021Day2
【ACM/NOI/CSP】NOI嘉年华 solution and code of NOI比赛经验分享&代码程序资源 ACM/NOI/CSP比赛经验分享&代码程序资源 说明:solution and code of NOI 文件列表: NOI嘉年华\NOI嘉年华.docx (61480, -04-26) NOI...
noi2010测试数据
noi2009测试数据
NOI 2021基础知识题库 NOI官网发布版.pdf
noi2006测试数据
noi2005测试数据
noi2008测试数据
AFO后发福利,noi模拟题(有代码,有解题报告,有大样例),可对拍
NOI笔试复习题.pdf
noi2002题目、标准程序、
noi2002测试数据
noi2001测试数据
NOI2011测试数据
NOI1991-2000测试数据
NOI 2012 测试数据 day1: random, bicycling, chess day2: park, delicacy, tritown
NOI2001~2009 (不含NOI2004) 原题题面。年代较为久远,整理供大家使用。题面全部来源于CCF。不含数据。