BZOJ_1269&&1507_[AHOI2006]文本编辑器editor&&[NOI2003]Editor
题意：
分析：
splay模拟即可
注意1507的读入格式，最好用getchar
代码：
1269：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 2097200
#define ls ch[p][0]
#define rs ch[p][1]
#define get(x) (ch[f[x]][1]==x)
int ch[N][2],f[N],siz[N],val[N],sz;
int S[N],top,tot,pos,turn[N],rt,n;
char opt[20],a[N];
void clear(int p){ ch[p][0]=ch[p][1]=f[p]=turn[p]=siz[p]=val[p]=0; }
int newnode(int v)
{
int p;
if(top)p=S[--top];
else p=++tot;
clear(p);
val[p]=v;siz[p]=1;
return p;
}
void pushup(int p){ if(p) siz[p]=siz[ls]+siz[rs]+1; }
void pushdown(int p)
{
if(turn[p])
{
turn[p]=0;turn[ls]^=1;turn[rs]^=1;
if(ls) swap(ch[ls][0],ch[ls][1]);
if(rs) swap(ch[rs][0],ch[rs][1]);
}
}
void rotate(int x)
{
int y=f[x],z=f[y],k=get(x);
ch[y][k]=ch[x][k^1];f[ch[y][k]]=y;ch[x][k^1]=y;
f[y]=x;f[x]=z;if(z) ch[z][ch[z][1]==y]=x;
pushup(y);pushup(x);if(rt==y)rt=x;
}
void splay(int x,int y){ for(int fa;(fa=f[x])!=y;rotate(x))if(f[fa]!=y)rotate((get(x)==get(fa))?fa:x); }
int find(int x)
{
int p=rt;
while(1) {
pushdown(p);
if(x<=siz[ls])p=ls;
else {
x-=siz[ls]+1;
if(!x)return p;
p=rs;
}
}
}
void rec(int p)
{
if(!p)return ;
if(ls)rec(ls);ls=0;
if(rs)rec(rs);rs=0;
clear(p);
S[top++]=p;
}
void build_merge(int fa,int l,int r,bool flg)
{
if(l>r)return ;
int mid=l+r>>1,p=newnode(a[mid]);
ch[fa][flg]=p;
f[p]=fa;
build_merge(p,l,mid-1,0);build_merge(p,mid+1,r,1);
pushup(p);
}
void insert(int x,int cnt)
{
int i;
char w;
/*for(i=1;i<=cnt;)
{
w=getchar();
if(w=='
'||w=='
')continue;
a[i++]=w;
}*/
gets(a+1);
//printf("%s
",a+1);
int p=x+1;
x=find(x);p=find(p);splay(x,0);splay(p,rt);
build_merge(p,1,cnt,0);
pushup(p);pushup(x);
}
void del(int x,int p)
{
x=find(x);p=find(p);
splay(x,0);splay(p,rt);
rec(ls);
ls=0;
pushup(p);pushup(x);
}
void reverse(int x,int p)
{
x=find(x);p=find(p);
splay(x,0);splay(p,rt);
turn[ls]^=1;swap(ch[ls][0],ch[ls][1]);
pushup(p);pushup(x);
}
void print()
{
printf("sz = %d
",sz);
for(int i=1;i<=sz;i++)printf("%c
",val[find(i)]);
}
int main()
{
scanf("%d",&n);
tot=sz=2;
ch[1][1]=2;
f[2]=1;
siz[1]=2;siz[2]=1;
rt=1;
pos++;
int i,x,y;
for(int i=1;i<=n;i++)
{
scanf("%s",opt);
if(opt[0]=='M'){
scanf("%d",&x);
pos=x+1;
}else if(opt[0]=='I'){
scanf("%d%*c",&x);
insert(pos,x);sz+=x;
//print();
}else if(opt[0]=='D'){
scanf("%d",&x);
del(pos,pos+x+1);sz-=x;
//print();
}else if(opt[0]=='R'){
scanf("%d",&x);
reverse(pos,pos+x+1);
//reverse(12,17);
//print();
}else if(opt[0]=='G'){
x=find(pos+1);
splay(x,0);
printf("%c
",val[x]);
}else if(opt[0]=='P'){
pos--;
}else{
pos++;
}
}
}
1507：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 2097200
#define ls ch[p][0]
#define rs ch[p][1]
#define get(x) (ch[f[x]][1]==x)
int ch[N][2],f[N],siz[N],val[N],sz;
int S[N],top,tot,pos,rt,n;
char opt[20],a[N];
void clear(int p){ ch[p][0]=ch[p][1]=f[p]=siz[p]=val[p]=0; }
int newnode(int v)
{
int p;
if(top)p=S[--top];
else p=++tot;
clear(p);
val[p]=v;siz[p]=1;
return p;
}
void pushup(int p){ if(p) siz[p]=siz[ls]+siz[rs]+1; }
void rotate(int x)
{
int y=f[x],z=f[y],k=get(x);
ch[y][k]=ch[x][k^1];f[ch[y][k]]=y;ch[x][k^1]=y;
f[y]=x;f[x]=z;if(z) ch[z][ch[z][1]==y]=x;
pushup(y);pushup(x);if(rt==y)rt=x;
}
void splay(int x,int y){ for(int fa;(fa=f[x])!=y;rotate(x))if(f[fa]!=y)rotate((get(x)==get(fa))?fa:x); }
int find(int x)
{
int p=rt;
while(1) {
if(x<=siz[ls])p=ls;
else {
x-=siz[ls]+1;
if(!x)return p;
p=rs;
}
}
}
void rec(int p)
{
if(!p)return ;
if(ls)rec(ls);ls=0;
if(rs)rec(rs);rs=0;
clear(p);
S[top++]=p;
}
void build_merge(int fa,int l,int r,bool flg)
{
if(l>r)return ;
int mid=l+r>>1,p=newnode(a[mid]);
ch[fa][flg]=p;
f[p]=fa;
build_merge(p,l,mid-1,0);build_merge(p,mid+1,r,1);
pushup(p);
}
void insert(int x,int cnt)
{
int i=0;
while(a[i+1]=getchar())
{
if(a[i+1]!=10&&a[i+1]!=13){
i++;if(i==cnt)break;
}
}
//printf("%s
",a+1);
int p=x+1;
x=find(x);p=find(p);splay(x,0);splay(p,rt);
build_merge(p,1,cnt,0);
pushup(p);pushup(x);
}
void del(int x,int p)
{
x=find(x);p=find(p);
splay(x,0);splay(p,rt);
rec(ls);
ls=0;
pushup(p);pushup(x);
}
void print(int p)
{
if(!p)return ;
if(ls>2)print(ls);
printf("%c",val[p]);
if(rs>2)print(rs);
}
int main()
{
scanf("%d",&n);
tot=sz=2;
ch[1][1]=2;
f[2]=1;
siz[1]=2;siz[2]=1;
rt=1;
pos++;
int i,x,y;
for(int i=1;i<=n;i++)
{
scanf("%s",opt);
//printf("%d
",i);
if(opt[0]=='M'){
scanf("%d",&x);
pos=x+1;
}else if(opt[0]=='I'){
scanf("%d",&x);
insert(pos,x);sz+=x;
}else if(opt[0]=='D'){
scanf("%d",&x);
if(pos+x+1>sz)x=sz-pos-1;
del(pos,pos+x+1);sz-=x;
}else if(opt[0]=='G'){
scanf("%d",&x);
int p=pos;
x=p+x+1;
p=find(p);
x=find(x);
splay(p,0);
splay(x,rt);
print(ch[x][0]);puts("");
}else if(opt[0]=='P'){
pos--;
}else{
pos++;
}
}
}