BZOJ1269: [AHOI2006]文本编辑器editor

Descriptio

这些日子,可可不和卡卡一起玩了,原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗?

为了明确任务目标,可可对“文本编辑器”做了一个抽象的定义: 

 文本:由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内,也就是说,这些字符均为可见字符或空格。光标:在一段文本中用于指示位置的标记,可以位于文本的第一个字符之前,文本的最后一个字符之后或文本的某两个相邻字符之间。文本编辑器:为一个可以对一段文本和该文本中的一个光标进行如下七条操作的程序。如果这段文本为空,我们就说这个文本编辑器是空的。 编写一个程序: 建立一个空的文本编辑器。 从输入文件中读入一些操作指令并执行。 对所有执行过的GET操作,将指定的内容写入输出文件。

Input

输入文件中第一行是指令条数N,以下是需要执行的N个操作。除了回车符之外,输入文件的所有字符的ASCII码都在闭区间[32, 126]内。且行尾没有空格。

Output

依次对应输入文件中每条GET指令的输出,不得有任何多余的字符。

Sample Input

10 Insert 13 Balanced eert Move 2 Delete 5 Next Insert 7 editor Move 0 Get Move 11 Rotate 4 Get

Sample Output

B t

HINT

对输入数据我们有如下假定: MOVE操作不超过50 000个,INSERT、DELETE和ROTATE操作作的总个数不超过6 000,GET操作不超过20 000个,PREV和NEXT操作的总个数不超过20 000。 所有INSERT插入的字符数之和不超过2M(1M=1 024*1 024)。 DELETE操作、ROTATE操作和GET操作执行时光标后必然有足够的字符。MOVE、PREV、NEXT操作不会把光标移动到非法位置。 输入文件没有错误。

Source

鸣谢seter重新制作数据

MDZZ块状链表好恶心。。

也没啥好讲的,就是个大暴力

不过网上好像没多少资料

有空整理一下吧

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<algorithm>
  6 using namespace std;
  7 const int MAXN=2000000+10;
  8 const int BlockSize=3000 + 100,BlockNum=3000 + 10;
  9 int Cur=0,head,tot;
 10 char str[MAXN];
 11 struct Block
 12 {
 13     int size,nxt;
 14     bool rev;
 15     char a[BlockSize];
 16     void Clear()
 17     {
 18         size=0;nxt=-1,rev=0;
 19     }
 20 }B[BlockNum];
 21 queue<int>q;//鐢ㄤ竴涓槦鍒楁潵缁存姢褰撳墠鏈夊摢浜涘潡
 22 int NewNode()
 23 {
 24     int t=q.front();q.pop();
 25     B[t].Clear();
 26     return t;
 27 }
 28 inline void Pre()
 29 {
 30     while(q.size()!=0)    q.pop();
 31     for(int i=0;i<BlockNum;i++) q.push(i);
 32     head = NewNode();
 33 }
 34 void Find(int &idx,int &cur)
 35 {
 36     while(idx!=-1&&cur>B[idx].size) cur-=B[idx].size,idx=B[idx].nxt;
 37 }
 38 void Pushdown(int idx)
 39 {
 40     if(B[idx].rev) 
 41     {
 42     //    for(int i=0;i<B[idx].size;i++)
 43     //        cout<<B[idx].a[i];cout<<endl;
 44         reverse(B[idx].a,B[idx].a+B[idx].size);
 45     //    for(int i=0;i<B[idx].size;i++)
 46     //        cout<<B[idx].a[i];cout<<endl;
 47         B[idx].rev=0;
 48     }
 49         
 50 }
 51 inline void Split(int idx,int cur)
 52 {
 53     if(idx==-1||cur==B[idx].size)    return ;
 54     Pushdown(idx);
 55     int tot=NewNode();
 56     memcpy(B[tot].a,B[idx].a+cur,sizeof(char) * (B[idx].size-cur) );
 57     B[tot].size=B[idx].size-cur;
 58     B[idx].size=cur;
 59     B[tot].nxt=B[idx].nxt;
 60     B[idx].nxt=tot;
 61 }
 62 void Delet(int idx)
 63 {
 64     q.push(idx);
 65 }
 66 void Merge(int idx)
 67 {
 68     for(int i=idx;i!=-1;i=B[i].nxt)
 69         for(int j=B[i].nxt;j!=-1;j=B[j].nxt)
 70         {
 71             if(B[i].size+B[j].size<=BlockSize)
 72             {
 73                 Pushdown(i);
 74                 Pushdown(j);
 75                 memcpy(B[i].a+B[i].size,B[j].a,sizeof(char) * B[j].size);
 76                 B[i].size+=B[j].size;B[i].nxt=B[j].nxt;
 77                 Delet(j);
 78             }
 79             else break;
 80         }
 81 }
 82 inline void Insert(int cur,int x,char *str)
 83 {
 84     int idx=head;
 85     Find(idx,cur);
 86     Split(idx,cur);
 87     int i=0;//宸茬粡鍔犲叆鐨勪釜鏁?
 88     while(i<x)
 89     {
 90         int Limit=min(BlockSize,x-i);
 91         int tot=NewNode();
 92         memcpy(B[tot].a,str+i,sizeof(char) * Limit);
 93         B[tot].size=Limit;
 94         B[tot].nxt=B[idx].nxt;
 95         B[idx].nxt=tot;
 96         idx=B[idx].nxt;
 97         i+=Limit;
 98     }
 99     Merge(head);
100 }
101 void Print(int cur)
102 {
103     int idx=head;
104     Find(idx,cur);
105     if(cur==B[idx].size) idx=B[idx].nxt,cur=0;
106     Pushdown(idx);
107     printf("%c\n",B[idx].a[cur]);
108 }
109 void Rever(int l,int r)
110 {
111     int idx=head;
112     Find(idx,l);
113     Split(idx,l);
114     int Start=idx,StartNxt=B[idx].nxt;
115     idx=head;
116     Find(idx,r);
117     Split(idx,r);
118     int EndNxt=B[idx].nxt;
119     int Tmp[BlockNum],cnt=0;
120     for(int i=StartNxt;i!=EndNxt;i=B[i].nxt)
121         B[i].rev^=1,Tmp[++cnt]=i;
122     Tmp[++cnt]=Start;Tmp[0]=EndNxt;
123     for(int i=cnt;i>=1;i--)
124         B[Tmp[i]].nxt=Tmp[i-1];
125     Merge(head);
126 }
127 void Dele(int l,int r)
128 {
129     int idx=head;
130     Find(idx,l);
131     Split(idx,l);
132     int Start=idx,StartNxt=B[idx].nxt;
133     idx=head;
134     Find(idx,r);
135     Split(idx,r);
136     int EndNxt=B[idx].nxt;
137     for(int i=StartNxt;i!=EndNxt;i=B[i].nxt)    Delet(i);
138     B[Start].nxt=EndNxt;
139     Merge(head);
140 }
141 int main()  
142 {
143     #ifdef WIN32
144     freopen("a.in","r",stdin);
145     #else
146     #endif
147     int N;scanf("%d",&N);
148     char opt[20];
149     Pre();
150     while(N--)
151     {
152         scanf("%s",opt);
153         if(opt[0]=='M') 
154             scanf("%d",&Cur);
155         else if(opt[0]=='I')
156         {
157             int len;
158             scanf("%d", &len);
159             int i = 0;
160             while(i < len) {char ch = getchar();if(ch >= 32 && ch <= 126) str[i++] = ch;}
161             str[i++] = '\0';
162             Insert(Cur,len,str);
163         }
164         else if(opt[0]=='D')
165         {
166             int x;
167             scanf("%d",&x);
168             Dele(Cur,Cur+x);
169         }
170         else if(opt[0]=='R')
171         {
172             int x;
173             scanf("%d",&x);
174             Rever(Cur,x+Cur);
175         }
176         else if(opt[0]=='G')    
177             Print(Cur);
178         else if(opt[0]=='P')    Cur--;
179         else if(opt[0]=='N')    Cur++;
180     }
181     return 0;
182 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

go语言的sql包原理与用法分析

本文实例讲述了go语言的sql包原理与用法。分享给大家供大家参考,具体如下: go的sql包是在pkg/database中,里面的两个包sql和sql/driv...

4436
来自专栏小勇DW3

Mybatis使用动态代理实现拦截器功能

  拦截器顾名思义为拦截某个功能的一个武器,在众多框架中均有“拦截器”。这个Plugin有什么用呢?或者说拦截器有什么用呢?可以想想拦截器是怎么实现的。Plug...

2832
来自专栏冰霜之地

高效的序列化/反序列化数据方式 Protobuf

上篇文章中其实已经讲过了 encode 的过程,这篇文章以 golang 为例,从代码实现的层面讲讲序列化和反序列化的过程。

4875
来自专栏偏前端工程师的驿站

MyBatis魔法堂:即学即用篇

一、前言                                          本篇内容以理解MyBatis的基本用法和快速在项目中实践为目的,...

2196
来自专栏芋道源码1024

Spring Webflux —— 源码阅读之 handler 包

查找给定请求的handler,如果找不到特定的请求,则返回一个空的Mono。这个方法被getHandler(org.springframework.web.se...

2935
来自专栏Hongten

JSP 九大内置对象

① out - javax.servlet.jsp.jspWriter    out对象用于把结果输出到网页上。

3702
来自专栏图像识别与深度学习

蓝牙项目开发心得

3219
来自专栏恰同学骚年

Hadoop学习笔记—7.计数器与自定义计数器

  在上图所示中,计数器有19个,分为四个组:File Output Format Counters、FileSystemCounters、File Input...

1022
来自专栏DOTNET

.Net多线程编程—Parallel LINQ、线程池

Parallel LINQ 1 System.Linq.ParallelEnumerable 重要方法概览: 1)public static ParallelQ...

2967
来自专栏数据结构与算法

BZOJ3261: 最大异或和(可持久化trie树)

1782

扫码关注云+社区