注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

【数据结构】文本编辑器  

2014-05-02 08:48:34|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
@BZOJ1269: [AHOI2006]文本编辑器editor

@BZOJ1507: [NOI2003]Editor

比较裸的数据结构题,用splay维护序列

一开始Build函数忘记return导致各种re

最神奇的是居然这样在我的电脑上还可以过所有测试点……

最后一开编译警告才发现问题……

话说splay真心比块状链表慢好多……也比rope慢……

难道是我的splay写得太渣?


#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1000000+1;
const int _MAX = 1000000000;
int n,m,Key=1;
char data[2040049+1];//?104805
int scani(){
int cc=' ';int fh=1,re=0;
while(cc==' '||cc=='\n'||cc=='\r') cc=getchar();
if(cc=='+'){cc=getchar();fh=1;}
if(cc=='+'){cc=getchar();fh=-1;}
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}
return re*fh;
}
void scans(char s[],int l){
char cc;
for(int i=1;l;i++,l--){
do{cc=getchar();}while(!(32<=cc&&cc<=126));
s[i]=cc;
}
}
struct Node{
int s;char c;short flag;
Node(){s=0;}
Node(Node *l){ch[0]=ch[1]=fa=l;s=0;flag=0;}
void down(){
if(flag) ch[0]->flag^=1,ch[1]->flag^=1;
if(flag){Node *l=ch[0];ch[0]=ch[1];ch[1]=l;flag=0;}
}
void count(){s=ch[1]->s+ch[0]->s+1;};
short pl(){return this==fa->ch[1];}
Node *ch[2],*fa;
}*null;
queue<Node*>pupa;
Node *newNode(){
if(pupa.empty()) return new Node(null);
Node *re=pupa.front();
pupa.pop();*re=Node(null);
return re;
}
void del(Node *&l){pupa.push(l);l=null;}
struct Splay{
public:
Node *ROOT;
void set(){
ROOT=newNode();
ROOT->ch[1]=newNode();ROOT->ch[1]->fa=ROOT;
ROOT->ch[1]->count();ROOT->count();
ROOT->c=ROOT->ch[1]->c=4;
}
private:
void rotate(Node *k){
k->down();
Node *r=k->fa;if(k==null||r==null) return;
int x=(k->pl()^1);
r->ch[x^1]=k->ch[x];
if(r->ch[x^1]!=null)r->ch[x^1]->fa=r;
if(r->fa!=null){r->fa->ch[r->pl()]=k;}
else ROOT=k;
k->ch[x]=r;
k->fa=r->fa;r->fa=k;
r->count();k->count();
}
void splay(Node *r,Node *tar=null){
if(r==null) return;
for(;r->fa!=tar;rotate(r))
if(r->fa->fa!=tar) rotate(r->pl()!=r->fa->pl()?r:r->fa);
}
Node *build(Node *fa,int l,int r){
if(r<l) return null;
int mid=(l+r)/2;
Node *ro = newNode();
ro->fa=fa;ro->c=data[mid];
if(l<r){
ro->ch[0]=build(ro,l,mid-1);
ro->ch[1]=build(ro,mid+1,r);
}ro->count();
return ro;
}
void remove(Node *&r){
if(r->ch[0]!=null)remove(r->ch[0]);
if(r->ch[1]!=null)remove(r->ch[1]);
del(r);
}
void Pack(int l,int r){
Node *ro;
ro=kth(ROOT,l);
splay(ro);
ro=kth(ROOT,r);
splay(ro,ROOT);
}
public:
void Rotate(int l){
Pack(Key,Key+1+l);
if(ROOT->ch[1]->ch[0]!=null)ROOT->ch[1]->ch[0]->flag^=1;//忘记判断重复标记
}
void Delete(int l){
Pack(Key,Key+1+l);
remove(ROOT->ch[1]->ch[0]);
ROOT->ch[1]->count();
ROOT->count();
}
void Insert(int l){
Pack(Key,Key+1);
ROOT->ch[1]->ch[0]=build(ROOT->ch[1],1,l);
ROOT->ch[1]->count();
ROOT->count();
}
Node *kth(Node *ro,int k){
while(ro!=null){
ro->down();
if(k<=ro->ch[0]->s) ro=ro->ch[0];
else if(k<=ro->ch[0]->s+1) return ro;
else {k-=ro->ch[0]->s+1;ro=ro->ch[1];}
}
printf("%c",5);
return 0;
}
void print(Node *r){
if(r==null)return;
r->down();
print(r->ch[0]);
printf("%c",r->c);
print(r->ch[1]);
}
void Print(int l,int r){
Pack(l,r+2);
print(ROOT->ch[1]->ch[0]);
}
}Stree;
int main(){
//freopen("input.txt","r",stdin);
//freopen("editor.in","r",stdin);
//freopen("editor.out","w",stdout);
int i,j,a;char ops[21];
null=newNode();*null=Node(null);
Stree.ROOT=null;
Stree.set();
n =scani();

for(i=1;i<=n;i++){
scanf("%s",ops);
if(ops[0]=='M'){
Key=scani()+1;
}else if(ops[0]=='I'){
a=scani();scans(data,a);
Stree.Insert(a);
}else if(ops[0]=='D'){
a=scani();
Stree.Delete(a);
}else if(ops[0]=='R'){
a=scani();
Stree.Rotate(a);
}else if(ops[0]=='G'){
Node *l=Stree.kth(Stree.ROOT,Key+1);
printf("%c\n",l->c);
//a=scani();
//Stree.Print(Key,Key+a-1);
//printf("\n");
}else if(ops[0]=='P'){
Key--;
}else if(ops[0]=='N'){
Key++;
}
//Stree.Print(1,Stree.ROOT->s-2);
//printf("\n");
}
return 0;
}

  评论这张
 
阅读(24)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017