【[AHOI2006]文本编辑器】

多了区间翻转，之后没了
区间翻转的标记记得在\(kth\)的时候下传
代码
#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define maxn 2100005

#define re register

int n,m,root,len,pos=1;

char val[maxn],S[maxn],opt[15];

int fa[maxn],sz[maxn],ch[maxn][2],rev[maxn];

inline void pushup(int x) {sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;}

inline void pushdown(int x) {

	if(!rev[x]) return;

	std::swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);

	std::swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);

	rev[x]=0,rev[ch[x][0]]^=1,rev[ch[x][1]]^=1;

}

inline void rotate(int x) {

	int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][k^1];

	ch[z][ch[z][1]==y]=x;ch[x][k^1]=y;ch[y][k]=w;

	pushup(y),pushup(x),fa[w]=y,fa[y]=x,fa[x]=z;

}

inline void splay(int x,int goal) {

	while(fa[x]!=goal) {

		int y=fa[x];

		if(fa[y]!=goal) rotate((ch[y][1]==x)^(ch[fa[y]][1]==y)?x:y);

		rotate(x);

	}

	if(!goal) root=x;

}

inline int kth(int now) {

	int x=root;

	while(1) {

		pushdown(x);

		if(sz[ch[x][0]]+1==now) return x;

		if(sz[ch[x][0]]>=now) x=ch[x][0];

			else now-=sz[ch[x][0]]+1,x=ch[x][1];

	}

}

int build(int x,int y,int f) {

	if(x>y) return 0;

	if(x==y) {

		fa[++m]=f,sz[m]=1,val[m]=S[x];

		return m;

	}

	int mid=x+y>>1,rt=++m;

	fa[rt]=f,val[rt]=S[mid];

	ch[rt][0]=build(x,mid-1,rt),ch[rt][1]=build(mid+1,y,rt);pushup(rt);

	return rt;

}

int main()

{

	scanf("%d",&n);

    root=1,sz[1]=2,ch[1][1]=2,sz[2]=1,fa[2]=1;m=2;

    while(n--) {

        scanf("%s",opt);

        if(opt[0]=='M') scanf("%d",&pos),pos++;

        if(opt[0]=='P') pos--;

        if(opt[0]=='N') pos++;

        if(opt[0]=='I') {

            scanf("%d",&len);S[0]=getchar();

            for(re int i=1;i<=len;i++) S[i]=getchar();

            int aa=kth(pos),bb=kth(pos+1);

            splay(aa,0),splay(bb,aa);

            int t=ch[root][1],rt=build(1,len,t);

            ch[t][0]=rt;pushup(t);splay(t,0);

        }

        if(opt[0]=='D') {

            scanf("%d",&len);

            int aa=kth(pos),bb=kth(pos+len+1);

            splay(aa,0),splay(bb,aa);

            ch[ch[root][1]][0]=0;pushup(ch[root][1]);splay(ch[root][1],0);

        }

        if(opt[0]=='G') {

        	int aa=kth(pos),bb=kth(pos+2);

			splay(aa,0),splay(bb,aa);

			putchar(val[ch[ch[root][1]][0]]);

			if(val[ch[ch[root][1]][0]]!=10) putchar(10);

		}

		if(opt[0]=='R') {

			scanf("%d",&len);

			int aa=kth(pos),bb=kth(pos+len+1);

			splay(aa,0),splay(bb,aa);

			int t=ch[ch[root][1]][0];

			std::swap(ch[t][1],ch[t][0]),rev[t]^=1;

		}

    }

	return 0;

}
巴特西

【[AHOI2006]文本编辑器】

最新文章

热门文章
