题解 P4567 【[AHOI2006]文本编辑器】

[原题传送门](https://www.luogu.org/problemnew/show/P4567) 毒瘤题。 一看题面:**这不是Splay/Treap乱搞题吗?** 于是乎乱搞28,WA两页多…… 总结了一下,本题的坑主要在输入,也就是**数据有些不严谨**。 题目中关于文本的定义 ``` 文本：由0个或多个字符构成的序列。这些字符的ASCII码在闭区间[32, 126]内，也就是说，这些字符均为可见字符或空格。 ``` 事实证明,**回车也算文本内容**。 按照这样定义的话,样例是没问题的。 输出回车的时候不用输出两个回车,只要一个即可(见代码)。 剩下的一个坑:数据中有**名称不对的操作**,应当忽略。 其余就是区间树基本操作,什么插入删除翻转之类。 区间树模板见:[P3391 【模板】文艺平衡树（Splay）](https://www.luogu.org/problemnew/show/P3391) **Code:** ```cpp #include<algorithm> #include<cstdio> #define MaxNum 2000010 using namespace std; int m,len; char ord[10]; struct Node {int l,r,c,g;char x;bool tag;}; struct Fhq_Treap { int tn,root,p; bool liv; Node a[MaxNum]; inline void ladd(int num){ if (a[num].tag){ a[a[num].r].tag^=1; a[a[num].l].tag^=1; swap(a[num].l,a[num].r); a[num].tag=0; } } inline void up(int num) {a[num].c=a[a[num].l].c+a[a[num].r].c+1;} inline void create(int x) { a[++tn].x=x; a[tn].g=(rand()<<4)^rand(); a[tn].c=1; } int marge(int x,int y){ if (!x||!y)return x+y; if (a[x].g<a[y].g){ ladd(x);a[x].r=marge(a[x].r,y); up(x);return x; }else{ ladd(y);a[y].l=marge(x,a[y].l); up(y);return y; } } void split(int num,int to,int &x,int &y){ if (!num)x=y=0; else { ladd(num); int mid=a[a[num].l].c+1; if (to>mid) {x=num;split(a[x].r,to-mid,a[x].r,y);} else {y=num;split(a[y].l,to,x,a[y].l);} up(num); } } void push(int len){ getchar(); int l,mid=0,r; for (int j=0;j<len;j++){ create(getchar()); mid=marge(mid,tn); }split(root,p,l,r); root=marge(marge(l,mid),r); } void change(int len){ int l,mid,r; split(root,p+len,l,r); split(l,p,l,mid); a[mid].tag^=1; root=marge(marge(l,mid),r); } void del(int len){ int l,mid,r; split(root,p+len,l,r); split(l,p,l,mid); root=marge(l,r); } void get(){ int x,mid,y; split(root,p+1,x,y); split(x,p,x,mid); if (a[mid].x!='\n') putchar(a[mid].x); putchar('\n'); root=marge(marge(x,mid),y); } }t; int main() { scanf("%d",&m); t.p=1; for (int i=1;i<=m;i++){ scanf("%s",ord); if (ord[0]=='I'){ scanf("%d",&len); t.push(len); }else if (ord[0]=='M'){ scanf("%d",&t.p);t.p++; }else if (ord[0]=='N')t.p++; else if (ord[0]=='P')t.p--; else if (ord[0]=='D'){ scanf("%d",&len); t.del(len); }else if (ord[0]=='G')t.get(); else if (ord[0]=='R'){ scanf("%d",&len); t.change(len); } }return 0; } ```