jzoj5249 【NOIP2017提高A组模拟8.10】文本编辑器 (序列修改类问题，数据结构)

题面

分析

splay的话是过不了最后一个点的。
显而易见的我们可以考虑链表+tag，但是细节很多。
因为翻转只翻转两个光标中间的地方，我们考虑将中间的放到一个队列里，然后左右两边分别开一个栈存。 (队列左右两边各留下n的空位以供插入)
翻转的话就调换一下队列的head与tail，并且将正方向取反。
+正方向就相当于在序列上的后一个位置。
想一想，这样设计的话别的操作不需要特殊考虑，和没翻转的情况一样做就行。
还需要考虑l,r光标反过来的情况。但数据里没有所以没打
怎么考虑呢？
假如当l=r时l右移或r左移，我们就交换l,r光标，并标记错位。这样的话后面l左移就相当于r左移，与一般的情况是等价的。错位的时候不能进行R操作。什么时候l=r了就将错位标记去掉。

两个套起来想有点复杂，需要好好思考。

单独维护光标区间，也是一些编辑器问题的套路。

Code

(不包括l,r错位的情况)

#include <cstdio>
#include <iostream>
#include <cstring>
#define getf(x) ((x=='L')?0:1)
const int N=4*1e6+10;

using namespace std;
char s[N],op;
int tot,root,len;
int top0,top1,L,R,tag;
char q[N*4],S[2][N];
int n,f[2],dir;

void show() {
for (int i=1; i<=top0; i++) putchar(S[0][i]);
for (int i=L; i!=R; i+=dir) putchar(q[i]);
    putchar(q[R]);
for (int i=top1; i; i--) putchar(S[1][i]);
    putchar('\n');
}
int readf() {char wf; scanf("%c",&wf); return getf(wf);}
int main() {
    freopen("33.in","r",stdin);
    freopen("33.out","w",stdout);
    scanf("%s\n%d",s+1,&n);
int len=strlen(s+1);
    f[0]=0,f[1]=len;
    L=R=n+1; for (int i=1; i<=len; i++) q[R++]=s[i];
    --R; dir=1;
//  show();

int w;
for (int i=1; i<=n; i++) {
        scanf("\n%c ",&op);
if (op!='R' && op!='S') w=readf();
if (op=='>') {
printf("%c\n",(f[w]==len)?'F':'T');
if (f[w]<len) {
                ++f[w];
if (w==0) S[0][++top0]=q[L],L+=dir;
else q[R+=dir]=S[1][top1--];
            }
        } else
if (op=='<') {
printf("%c\n",(f[w]==0)?'F':'T');
if (f[w]>0) {
                --f[w];
if (w==0) q[L-=dir]=S[0][top0--];
else S[1][++top1]=q[R],R-=dir;
            }
        } else
if (op=='I') {
            char ne; scanf(" %c",&ne);
if (w==0) S[0][++top0]=ne; else 
q[R+=dir]=ne;
printf("T\n");
if (w==0) {
if (f[1]>=f[0]) ++f[1];
                ++f[0]; 
            } else {
if (f[0]>=f[1]) ++f[0];
                ++f[1];
            }
            ++len;
        } else 
if (op=='D') {
if (f[w]==len) {
printf("F\n"); continue;
            } else printf("T\n");
if (w==0) L+=dir; else 
                top1--;
if (w==0) {
if (f[1]>f[0]) --f[1];
            } else {
if (f[0]>f[1]) --f[0];
            }
            --len;
        } else 
if (op=='R') {
if (tag) {
printf("F\n"); continue;
            } else printf("T\n");
            swap(L,R); dir=-dir;
        } else 
if (op=='S') show(),printf("\n");
//      printf("\n%d ",i);
//      show();
//      printf("\n");
    }
}