题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1269
跟NOI03的那道editor没什么区别,只是多维护一个Reverse(翻转)标记,旋转的时候记得下传标记。
代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define MAXN 2000010
#define L(t) T[t].Left
#define R(t) T[t].Right
#define S(t) T[t].Size
#define C(t) T[t].Char
#define update(t) S(t)=S(L(t))+S(R(t))+1
#define Cl(r,t) (r<S(L(t)))
#define Ls(t) T[t].Lay
struct node {
int Left,Right,Size,Char;
bool Lay;
node () {
Left=Right=Size=Char=0;
Lay=false;
}
} T[MAXN];
int n,roof=0,M=0;
int s[MAXN];
void pushdown(int t) {
if (t&&Ls(t)) {
swap(L(t),R(t));
Ls(t)^=true,Ls(L(t))^=true,Ls(R(t))^=true;
}
}
void zag(int &t) {
pushdown(t);pushdown(R(t));
int k=R(t);
R(t)=L(k);update(t);
L(k)=t;update(k);
t=k;
}
void zig(int &t) {
pushdown(t);pushdown(L(t));
int k=L(t);
L(t)=R(k);update(t);
R(k)=t;update(k);
t=k;
}
bool splay(int r,int &t,bool flag) {
pushdown(t);
if (r==S(L(t))) return false;
bool w=splay(Cl(r,t)?r:r-S(L(t))-1,Cl(r,t)?L(t):R(t),true);
if (w) {
if (Cl(r,t)) {
if (Cl(r,L(t))) zig(t); else zag(L(t));
zig(t);
} else {
if (!Cl(r-S(L(t))-1,R(t))) zag(t); else zig(R(t));
zag(t);
}
} else if (!flag) if (Cl(r,t)) zig(t);else zag(t);
return w^true;
}
void build(int l,int r,int &t) {
if (l>r) { t=0; return ; }
int mid=(l+r)>>1;
C(t=++M)=s[mid];
S(t)=r-l+1;
build(l,mid-1,L(t)),build(mid+1,r,R(t));
update(t);
}
void getstring(int N) {
int ch;
for (int i=0;i++<N;) {
for (ch=getchar();ch=='\n';ch=getchar()) ;
s[i]=ch;
}
}
int main() {
scanf("%d\n",&n);
roof=++M;R(roof)=++M;
C(1)=C(2)=int('$');
while (n--) {
char st[20];
int m,Tr;
scanf("%s",&st);
switch (st[0]) {
case'M':
scanf("%d",&m);
splay(m,roof,false);
break;
case'I':
Tr=0;
scanf("%d",&m);
getstring(m);
build(1,m,Tr);
splay(0,R(roof),false);
L(R(roof))=Tr;
update(R(roof));
update(roof);
break;
case'D':
scanf("%d",&m);
splay(min(m,S(R(roof))-1),R(roof),false);
L(R(roof))=0;
update(R(roof));
update(roof);
break;
case'G':
pushdown(roof);
splay(0,R(roof),false);
printf("%c\n",char(C(R(roof))));
break;
case'P':
splay(S(L(roof))-1,roof,false);
break;
case'N':
splay(S(L(roof))+1,roof,false);
break;
case'R':
scanf("%d",&m);
splay(m,R(roof),false);
Ls(L(R(roof)))^=true;
break;
}
}
return 0;
}
网友评论