原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1269
伸展树的运用，如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::swap;
const int Max_N = ;
struct Node{
char chr;
int s;
bool rev;
Node *pre, *ch[];
inline void
set(char _chr = ' ', int _s = , Node *p = NULL){
chr = _chr, s = _s, rev = ;
pre = ch[] = ch[] = p;
}
inline void push_up(){
s = ch[]->s + ch[]->s + ;
}
inline void update(){
rev ^= ;
swap(ch[], ch[]);
}
inline void push_down(){
if (rev != ){
rev ^= ;
ch[]->update();
ch[]->update();
}
}
};
struct SplayTree{
char buf[Max_N];
Node *tail, *root, *null;
Node stack[Max_N], *store[Max_N];
int top, pos;
void init(){
top = , pos = ;
tail = &stack[];
null = tail++;
null->set();
root = newNode(' ');
root->ch[] = newNode(' ');
root->ch[]->pre = root;
root->ch[]->push_up();
root->push_up();
}
inline Node *newNode(char chr){
Node *p = null;
if (!top) p = tail++;
else p = store[--top];
p->set(chr, , null);
return p;
}
inline void rotate(Node *x, int c){
Node *y = x->pre;
y->push_down(), x->push_down();
y->ch[!c] = x->ch[c];
x->pre = y->pre;
if (x->ch[c] != null) x->ch[c]->pre = y;
if (y->pre != null) y->pre->ch[y->pre->ch[] != y] = x;
x->ch[c] = y;
y->pre = x;
y->push_up();
if (y == root) root = x;
}
inline void splay(Node *x, Node *f){
if (x == root) return;
for (; x->pre != f; x->push_down()){
if (x->pre->pre == f){
rotate(x, x->pre->ch[] == x);
} else {
Node *y = x->pre, *z = y->pre;
if (z->ch[] == y){
if (y->ch[] == x)
rotate(y, ), rotate(x, );
else rotate(x, ), rotate(x, );
} else {
if (y->ch[] == x)
rotate(y, ), rotate(x, );
else rotate(x, ), rotate(x, );
}
}
}
x->push_up();
}
inline Node *built(int l, int r){
if (l > r) return null;
int mid = (l + r) >> ;
Node *p = newNode(buf[mid]);
p->ch[] = built(l, mid - );
if (p->ch[] != null) p->ch[]->pre = p;
p->ch[] = built(mid + , r);
if (p->ch[] != null) p->ch[]->pre = p;
p->push_up();
return p;
}
inline void recycle(Node *x){
if (x != null){
recycle(x->ch[]);
store[top++] = x;
recycle(x->ch[]);
}
}
inline Node *select(Node *x, int k){
for (int t = ; x != null;){
x->push_down();
t = x->ch[]->s;
if (k == t + ) break;
else if (k <= t) x = x->ch[];
else k -= t + , x = x->ch[];
}
return x;
}
inline void get_range(int x, int y){
splay(select(root, x + ), null);
splay(select(root, y + ), root);
}
inline void Gets(char *s){
char c;
while (c = getchar(), c != '\n') *s++ = c;
*s = '\0';
}
inline void insert(int n){
char c;
scanf("%c", &c);
Gets(buf + );
get_range(pos, pos);
Node *ret = built(, n);
root->ch[]->ch[] = ret;
ret->pre = root->ch[];
root->ch[]->push_up();
root->push_up();
}
inline void del(int n){
get_range(pos, pos + n);
Node* &ret = root->ch[];
ret->ch[]->pre = null;
#ifdef LOCAL
recycle(ret->ch[]);
#endif
ret->ch[] = null;
ret->push_up();
root->push_up();
}
inline void rotate(int n){
get_range(pos, pos + n);
root->ch[]->ch[]->update();
}
inline void get(){
splay(select(root, pos + ), null);
printf("%c\n", root->chr);
}
inline void move(){
scanf("%d", &pos);
}
inline void prev(){
pos--;
}
inline void next(){
pos++;
}
}spt;
int main(){
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w+", stdout);
#endif
spt.init();
int m, n;
char str[];
scanf("%d", &m);
while (m--){
scanf("%s", str);
switch (str[]){
case 'M':
spt.move();
break;
case 'I':
scanf("%d", &n);
spt.insert(n);
break;
case 'D':
scanf("%d", &n);
spt.del(n);
break;
case 'N':
spt.next();
break;
case 'P':
spt.prev();
break;
case 'R':
scanf("%d", &n);
spt.rotate(n);
break;
case 'G':
spt.get();
break;
}
}
return ;
}