当前位置：网站首页>bzoj1507 [NOI2003]Editor

bzoj1507 [NOI2003]Editor

2022-08-08 16:22:00 【51CTO】


​ ​http://www.elijahqi.win/2018/01/23/bzoj1507-noi2003editor/​​ ‎

Description


Input

输入文件editor.in的第一行是指令条数t，以下是需要执行的t个操作。其中： 为了使输入文件便于阅读，Insert操作的字符串中可能会插入一些回车符，请忽略掉它们（如果难以理解这句话，可以参考样例）。 除了回车符之外，输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。 这里我们有如下假定：  MOVE操作不超过50000个，INSERT和DELETE操作的总个数不超过4000，PREV和NEXT操作的总个数不超过200000。  所有INSERT插入的字符数之和不超过2M（1M=1024*1024），正确的输出文件长度不超过3M字节。  DELETE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作必然不会试图把光标移动到非法位置。  输入文件没有错误。 对C++选手的提示：经测试，最大的测试数据使用fstream进行输入有可能会比使用stdio慢约1秒。
Output

输出文件editor.out的每行依次对应输入文件中每条GET指令的输出。
Sample Input
15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 15
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22
Sample Output
.\/.
abcde^_^f.\/.ghijklmno
当年icefox嫌弃太简单就没写的题orz orz
写完之后去翻了翻题解 发现脑洞真大 什么deque 分块 都直接爆踩蒟蒻我的splay 我好菜qwq
这题 是平衡树的一些操作 至于这个移动因为题目保证合法 所以 我只需要直接改动我的指针的位置即可 这题感觉甚是恶心 读入的时候一开始样例就过不去 搜了下题解 看到读入的时候必须scanf(“%d%*c)酱 似乎是为了跳过后面的一个字符..

      
      

       
       #include<cstdio>
       
       
#include<cstring>
       
       
#include<algorithm>
       
       
#define N 2200000 
       
       
using namespace std;
       
       
int id[N],n,size[N],fa[N],c[N][2],rev[N],root,cnt;
       
       
char op[10],v[N],ch[N];
       
       
inline void update(int x){
       
       
    size[x]=size[c[x][0]]+size[c[x][1]]+1;
       
       
}
       
       
inline void build(int f,int l,int r){
       
       
    if (l>r) return;
       
       
    int mid=l+r>>1;int now=id[mid];v[now]=ch[mid];
       
       
    fa[now]=id[f];c[id[f]][mid>f]=now;v[now]=ch[mid];
       
       
    if (l==r){size[now]=1;return;}
       
       
    build(mid,l,mid-1);build(mid,mid+1,r);update(id[mid]);
       
       
}
       
       
inline int find(int x,int sz){
       
       
    int l=c[x][0],r=c[x][1];if(size[l]+1==sz) return x;
       
       
    if (sz<=size[l]) return find(l,sz);else return find(r,sz-size[l]-1);
       
       
}
       
       
inline void rotate(int x,int &tar){
       
       
    int y=fa[x],z=fa[y];
       
       
    if (y==tar) tar=x;else c[z][c[z][1]==y]=x;
       
       
    int l=c[y][1]==x,r=l^1;
       
       
    fa[x]=z;fa[c[x][r]]=y;fa[y]=x;
       
       
    c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
       
       
}
       
       
inline void splay(int x,int &tar){
       
       
    while(x!=tar){
       
       
        int y=fa[x],z=fa[y];
       
       
        if (y!=tar) {
       
       
            if(c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar);
       
       
        }rotate(x,tar);
       
       
    }
       
       
}
       
       
inline int split(int x,int y){
       
       
    int xx=find(root,x),yy=find(root,y);
       
       
    splay(yy,root);splay(xx,c[root][0]);return c[xx][1];
       
       
}
       
       
inline void print(int x){
       
       
    if (c[x][0]) print(c[x][0]);
       
       
    printf("%c",v[x],size[x]);
       
       
    if(c[x][1]) print(c[x][1]);
       
       
}
       
       
int main(){
       
       
    freopen("bzoj1507.in","r",stdin);
       
       
    scanf("%d",&n);id[1]=1;id[2]=2;cnt=2;
       
       
    build(0,1,2);int pos=1,x=0;root=id[1];
       
       
    for (int i=1;i<=n;++i){
       
       
        scanf("%s",op);
       
       
        if (op[0]=='I'){
       
       
            scanf("%d%*c",&x);int st=0;
       
       
            while(1){
       
       
                ch[st+1]=getchar();
       
       
                if (ch[st+1]!='\n'&&ch[st+1]!='\r') {++st;if (st==x) break;}
       
       
            }for (int i=1;i<=x;++i) id[i]=++cnt;build(0,1,x);
       
       
            int xx=find(root,pos),yy=find(root,pos+1);splay(yy,root);splay(xx,c[root][0]);
       
       
            int now=id[1+x>>1];fa[now]=xx;c[xx][1]=now;update(xx);splay(now,root);//printf("%d\n",root);
       
       
        }//print(root);puts("");
       
       
        if (op[0]=='M') {scanf("%d",&x);pos=x+1;}
       
       
        if (op[0]=='P') --pos;if (op[0]=='N') ++pos;
       
       
        if (op[0]=='D'){
       
       
            scanf("%d",&x);
       
       
            int tmp=split(pos,pos+x+1);c[fa[tmp]][1]=0;update(fa[tmp]);splay(fa[tmp],root);
       
       
        }
       
       
        if (op[0]=='G'){scanf("%d",&x);int tmp=split(pos,pos+x+1);print(tmp);puts("");}
       
       
    }
       
       
    return 0;
       
       
}
       
       

      
      

      
      
    
       
       
  • 1.
    • 
       
       
  • 2.
    • 
       
       
  • 3.
    • 
       
       
  • 4.
    • 
       
       
  • 5.
    • 
       
       
  • 6.
    • 
       
       
  • 7.
    • 
       
       
  • 8.
    • 
       
       
  • 9.
    • 
       
       
  • 10.
    • 
       
       
  • 11.
    • 
       
       
  • 12.
    • 
       
       
  • 13.
    • 
       
       
  • 14.
    • 
       
       
  • 15.
    • 
       
       
  • 16.
    • 
       
       
  • 17.
    • 
       
       
  • 18.
    • 
       
       
  • 19.
    • 
       
       
  • 20.
    • 
       
       
  • 21.
    • 
       
       
  • 22.
    • 
       
       
  • 23.
    • 
       
       
  • 24.
    • 
       
       
  • 25.
    • 
       
       
  • 26.
    • 
       
       
  • 27.
    • 
       
       
  • 28.
    • 
       
       
  • 29.
    • 
       
       
  • 30.
    • 
       
       
  • 31.
    • 
       
       
  • 32.
    • 
       
       
  • 33.
    • 
       
       
  • 34.
    • 
       
       
  • 35.
    • 
       
       
  • 36.
    • 
       
       
  • 37.
    • 
       
       
  • 38.
    • 
       
       
  • 39.
    • 
       
       
  • 40.
    • 
       
       
  • 41.
    • 
       
       
  • 42.
    • 
       
       
  • 43.
    • 
       
       
  • 44.
    • 
       
       
  • 45.
    • 
       
       
  • 46.
    • 
       
       
  • 47.
    • 
       
       
  • 48.
    • 
       
       
  • 49.
    • 
       
       
  • 50.
    • 
       
       
  • 51.
    • 
       
       
  • 52.
    • 
       
       
  • 53.
    • 
       
       
  • 54.
    • 
       
       
  • 55.
    • 
       
       
  • 56.
    • 
       
       
  • 57.
    • 
       
       
  • 58.
    • 
       
       
  • 59.
    • 
       
       
  • 60.
    • 
       
       
  • 61.
    • 
       
       
  • 62.
    • 
       
       
  • 63.
    • 
       
       
  • 64.
    • 
       
       
  • 65.
    • 
       
       
  • 66.
    • 
       
       
  • 67.
    • 
       
       
  • 68.
    • 
       
       
  • 69.
    • 
       
       
  • 70.
    •


原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5556238

边栏推荐

猜你喜欢

随机推荐