[数据结构与算法][NOI2003]文本编辑器

文本编辑器

恶心人的大模拟（？or 平衡树），发现我两年前就一直卡着没过，今天写过了发一发题解

我们明显维护一个可以动态插入删除字符，并查询一段区间字符的数据结构，这不就是平衡树吗。
所以打FHQ_Treap! 既然教练叫用$Splay$做，那就用$Splay$吧。还是别用$Spaly$。

对于光标位置的操作$1,5,6$，我们只需要单独记录一个指针维护光标的位置。
而关于字符串的操作$2,3,4$设计到区间插入，删除之类的操作，显然我们需要将一棵$Splay$按大小分为两段的操作与将两棵$Splay$合并在一起的操作。
显然，分成两段我们只需要将要分割的那个点旋到根，再将根与它的儿子分裂成两棵$Splay$。
而合并，我们只需要将一棵树的最左端点旋到根，这样根就没左儿子了，将另一棵$Splay$接在上面即可。
简单易懂的操作，之后就跟$FHQ\_Treap$的操作一样了 ，这大家都会吧，也没什么好解释的，就是先把要操作的区间分出来，处理后再合并回去而已 。

时间复杂度$O\left(n\log n+M\right)$，$M$是总字符数。
注意，输入数据中不在ASCII$[32,126]$之内的字符是不能出现在文本中的，输入中出现了就删掉。

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN ((1<<21)+5)
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int inv2=499122177;
const int jzm=2333;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,stak;char str[MAXN];
struct ming{
	int ch[2],fa,siz;char val;
	ming(){ch[0]=ch[1]=fa=val=siz=0;}
}; 
class Splay{
	#define root tr[0].ch[1]
	private:
		ming tr[MAXN];int tot;
		void pushup(int rt){tr[rt].siz=tr[tr[rt].ch[0]].siz+tr[tr[rt].ch[1]].siz+1;}
		int identify(int rt){return tr[tr[rt].fa].ch[0]!=rt;}
		void link(int rt,int f,int d){tr[rt].fa=f;tr[f].ch[d]=rt;}
		void rotate(int x){
			int y=tr[x].fa,z=tr[y].fa,d1=identify(y),d2=identify(x),B=tr[x].ch[d2^1];
			link(B,y,d2);link(y,x,d2^1);link(x,z,d1);pushup(y);pushup(x);
		}
		void splay(int x,int y){
			y=tr[y].fa;
			while(tr[x].fa!=y){
				int z=tr[x].fa;
				if(tr[z].fa==y)rotate(x);
				else if(identify(z)==identify(x))rotate(z),rotate(x);
				else rotate(x),rotate(x);
			}
			if(!y)root=x;
		}
		int newnode(char w){int rt=++tot;tr[rt].val=w;tr[rt].siz=1;return rt;}
		int getRoot(){return root;}
		int build(int l,int r){
			int mid=l+r>>1,rt=newnode(str[mid]);
			if(l<mid)link(build(l,mid-1),rt,0);
			if(r>mid)link(build(mid+1,r),rt,1);
			pushup(rt);
			return rt;
		}
		int findNum(int &rt,int k){
			int now=rt;
			while(k){
				if(k==tr[tr[now].ch[0]].siz+1)break;
				if(k<=tr[tr[now].ch[0]].siz)now=tr[now].ch[0];
				else k-=tr[tr[now].ch[0]].siz+1,now=tr[now].ch[1];
			}
			splay(now,rt);rt=now;return now;
		}
		void split(int now,int k,int &x,int &y){
			if(!now){x=y=0;return ;}
			if(!k){x=0;y=now;return ;}
			x=findNum(now,k),y=tr[x].ch[1];
			tr[x].ch[1]=tr[y].fa=0;pushup(x);
		}
		int merge(int x,int y){
			if(!x||!y)return x+y;
			int z=findNum(y,1);link(x,z,0);pushup(z);
			return z;
		}
		void Print(int rt){
			if(tr[rt].ch[0])Print(tr[rt].ch[0]);
			putchar(tr[rt].val);
			if(tr[rt].ch[1])Print(tr[rt].ch[1]);
		}
	public:
		void Insert(int x){
			int x1,y1;split(root,x,x1,y1);
			link(merge(x1,merge(build(1,stak),y1)),0,1);
		}
		void Remove(int x,int y){
			int x1,y1,x2,y2;split(root,y,x1,y1);
			split(x1,x-1,x2,y2);link(merge(x2,y1),0,1);
		}
		void Get(int x,int y){
			int x1,y1,x2,y2;split(root,y,x1,y1);
			split(x1,x-1,x2,y2);Print(y2);puts("");
			link(merge(merge(x2,y2),y1),0,1);
		}
	#undef root
}T;
int now;
signed main(){
	read(n);now=0;int tot=0;
	for(int i=1;i<=n;i++){
		char opt[10]={};scanf("\n%s",opt+1);
		if(opt[1]=='M'){int k;read(k);now=k;}
		if(opt[1]=='I'){
			read(stak);
			for(int i=1;i<=stak;i++){
				str[i]=getchar();
				if(str[i]=='\n'||str[i]=='\r')i--;	
			}
			T.Insert(now);tot+=stak;
		}
		if(opt[1]=='D'){int len;read(len);T.Remove(now+1,now+len);tot-=len;}
		if(opt[1]=='G'){int len;read(len);T.Get(now+1,now+len);}
		if(opt[1]=='P')now=max(now-1,0);
		if(opt[1]=='N')now=min(now+1,tot);
	}
	return 0;
}

谢谢！！！