转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
通过一个变量记录光标的位置即可。
MOVE:直接改变光标位置变量
INSERT:经典旋转,插入到根的右孩子的左子树
ROTATE:经典操作,区间反转,通过一个延迟标记记录,交换左右子树。同样要用到经典的旋转
GET:得到光标位置的后继,可以GET_KTH后然后GET_NEXT,也可以直接旋转,或者旋转后GET_MIN
PREV,NEXT:都只需要改变光标位置变量
在指定旋转的时候,我用的是GET_KTH,找到位置然后再Splay旋转,也有直接旋转的,代码里也加了
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
#define N 1024*1024*2
#define inf 1<<29
#define MOD 100000007
#define LL long long
#define Key_value ch[ch[root][1]][0]
#define _match(a,b) ((a)==(b))
using namespace std;
int n,q;
char key[N];
int size[N],pre[N],rev[N],pos;
int ch[N][2],tot,root,node[N];
//debug部分copy from hh
void Treaval(int x) {
if(x) {
Treaval(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2c \n",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]);
Treaval(ch[x][1]);
}
}
void debug() {printf("%d\n",root);Treaval(root);}
//以上Debug
void NewNode(int &r,char k,int father){
r=++tot;
ch[r][0]=ch[r][1]=0;
pre[r]=father;
rev[r]=0;
key[r]=k;
}
void Push_Up(int r){
size[r]=size[ch[r][0]]+size[ch[r][1]]+1;
}
void Push_Down(int r){
if(rev[r]){
swap(ch[r][0],ch[r][1]);
rev[ch[r][0]]^=1;
rev[ch[r][1]]^=1;
rev[r]=0;
}
}
void Bulid(int &r,int L,int R,int father,char *str){
if(L>R)
return ;
int mid=(L+R)/2;
NewNode(r,str[mid],father);
Bulid(ch[r][0],L,mid-1,r,str);
Bulid(ch[r][1],mid+1,R,r,str);
Push_Up(r);
}
void Init(){
tot=root=0;
ch[root][0]=ch[root][1]=pre[root]=rev[root]=size[root]=0;
Bulid(root,0,4,0," ");
}
void Rotate(int x,int kind){
int y=pre[x];
Push_Down(y);
Push_Down(x);
ch[y][!kind]=ch[x][kind];
pre[ch[x][kind]]=y;
if(pre[y])
ch[pre[y]][ch[pre[y]][1]==y]=x;
pre[x]=pre[y];
ch[x][kind]=y;
pre[y]=x;
Push_Up(y);
}
void Splay(int r,int goal){
Push_Down(r);
while(pre[r]!=goal){
if(pre[pre[r]]==goal)
Rotate(r,ch[pre[r]][0]==r);
else{
int y=pre[r];
int kind=(ch[pre[y]][0]==y);
if(ch[y][kind]==r){
Rotate(r,!kind);
Rotate(r,kind);
}
else{
Rotate(y,kind);
Rotate(r,kind);
}
}
}
Push_Up(r);
if(goal==0) root=r;
}
void RotateTo(int k,int goal) {
int r=root;
Push_Down(r);
while(size[ch[r][0]]!=k){
if(k<size[ch[r][0]]){
r=ch[r][0];
} else {
k-=(size[ch[r][0]]+1);
r=ch[r][1];
}
Push_Down(r);
}
Splay(r,goal);
}
int Get_Kth(int r,int k){
Push_Down(r);
int t=size[ch[r][0]]+1;
if(t==k)
return r;
if(t>k)
return Get_Kth(ch[r][0],k);
else
return Get_Kth(ch[r][1],k-t);
}
int Get_Min(int r){
Push_Down(r);
while(ch[r][0]){
r=ch[r][0];
Push_Down(r);
}
return r;
}
int Get_Max(int r){
Push_Down(r);
while(ch[r][1]){
r=ch[r][1];
Push_Down(r);
}
return r;
}
void Reversal(int k){
int x=Get_Kth(root,pos);
Splay(x,0);
int y=Get_Kth(root,pos+k+1);
Splay(y,root);
rev[Key_value]^=1;
}
void Cut(int a,int b,int c){
int x=Get_Kth(root,a);
int y=Get_Kth(root,b+2);
Splay(x,0);
Splay(y,root);
int tmp=Key_value;
Key_value=0;
Push_Up(ch[root][1]);
Push_Up(root);
int z=Get_Kth(root,c+1);
Splay(z,0);
int m=Get_Min(ch[root][1]);
Splay(m,root);
Key_value=tmp;
pre[Key_value]=ch[root][1];
Push_Up(ch[root][1]);
Push_Up(root);
}
int cnt;
void InOrder(int r){
if(r==0)
return;
Push_Down(r);
InOrder(ch[r][0]);
if(cnt>=1&&cnt<=size[root]-5)
printf("%c",key[r]);
cnt++;
InOrder(ch[r][1]);
}
void Insert(char *str){
int len=strlen(str);
int x=Get_Kth(root,pos);
Splay(x,0);
// RotateTo(pos,0);
int m=Get_Min(ch[root][1]);
Splay(m,root);
Bulid(Key_value,0,len-1,ch[root][1],str);
}
void Delete(int k){
// RotateTo(pos,0);
int x=Get_Kth(root,pos);
Splay(x,0);
int y=Get_Kth(root,pos+k+1);
Splay(y,root);
pre[Key_value]=0;
Key_value=0;
Push_Up(ch[root][1]);
Push_Up(root);
}
char Get_Answer(){
int x=Get_Kth(root,pos);
Splay(x,0);
// RotateTo(pos,0);
int y=Get_Min(ch[root][1]);
return key[y];
}
char str[N];
int main(){
//freopen("editor1.in","r",stdin);
while(scanf("%d",&q)!=EOF){
Init();
int k;
pos=1;//光标初始位置
while(q--){
scanf("%s",str,&k);
if(str[0]=='I'){
scanf("%d",&k);
getchar();
gets(str);
Insert(str);
}
else if(str[0]=='M'){
scanf("%d",&k);
pos=k+1;
}
else if(str[0]=='D'){
scanf("%d",&k);
Delete(k);
}
else if(str[0]=='R'){
scanf("%d",&k);
Reversal(k);
}
else if(str[0]=='G')
printf("%c\n",Get_Answer());
else if(str[0]=='P')
pos--;
else
pos++;
}
}
return 0;
}
分享到:
相关推荐
ahoi2012年测试数据,安徽省中学组竞赛测试数据
AHOI2009的试题和测试数据,如果有人需要可以看看。
安徽省选AHOI2001-2012试题及数据
ahoi2012试题 安徽省2012年信息学竞赛试题
pyh提供,只是顺手转载。。。。 安徽2009NOI省选数据..
洛谷P4248 [AHOI2013]差异 的 AC 代码
好论文 关于安徽的比赛情况的介绍的 希望下载啊
LOJLOJLOJ 传送门 题解:首先考虑一棵树怎么做,就是树形 dpdpdp,然后我们可以枚举每一条边怎么选,显然有 3 种情况 进一步发现只需要枚举两种,即强制 uuu 选 vvv 不选,和强制 uuu 不选 vvv 随意 ...
作为一个计算机科学家,JYY有一套黑白色的拼图,他希望通过合理的拼接,使得拼出的最终图案中,能包含面积最大的全白色子矩形。之后JYY发现,可以通过改变这S块拼图
【故事背景】宅男JYY非常喜欢玩RPG游戏,比如仙剑,轩辕剑等等。不过JYY喜欢的并不是战斗场景,而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的
本资源是安徽省信息学奥林匹克OI2012省选资料,内容详实,适合准备参加省选项的高中生。
AOI安徽省青少年信息学奥林匹克竞赛小学组试题 汇总 包含了2014;2013,2011,2010年的试题。
FRAFOS GmbH | Windscheidstr. 18 Ahoi 10627 Berlin Germany | info@frafos.com | ww
最小割性质【AHOI2009】 消圈定理 数据结构 树状斑点 线段树 划分树 平衡树(fhqtreap / splay) LCT 并查集 树 可并堆 可持久化数据结构 数学 数论 gcd / exgcd 费马(线性推逆元)/(EX)欧拉定理 米勒·拉宾...
目录[TJOI2017]可乐[ZJOI2006]物流运输[HNOI/AHOI2018]道路[ZJOI2007]时态同步[TJOI2017]城市 [TJOI2017]可乐 tag上是分层图+矩阵优化,但是被我用暴力+滚动数组水过去了(赞美O2!)对每个点有三种状态,0:上一秒...
coremedia-tools (c) Alexander Lenzen,Ahoi-IT。 mailto-name: al, mailto-domain: ahoi-it.de 有关许可信息,请参阅LICENSE.md 。目的这是一个 CoreMedia 命令行工具包。内容僵尸杀手Zombie-Killer 是一个工具,...
2023安徽“科大国创杯”小学组 试题