一不小心又开启了每天昏迷24个小时的状态，脑子不清醒的时候就该去看动画片。

只需要记录光标的位置即可，剩下的就是Splay的经典操作了，不多说了，我只是为了测试模板。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 9999991

using namespace std;

const int MAXN = 3001000;

struct N
{
    //info
    int son[2],pre;

    //data
    char data;
    int mark;
    int ls,rs,s;
} st[MAXN];

int Top;

char s[MAXN];

void Push_Down(int root)
{
    if(st[root].mark == 1)
    {
        st[root].mark = 0;

        if(st[root].son[0] != -1)
            st[st[root].son[0]].mark ^= 1;
        if(st[root].son[1] != -1)
            st[st[root].son[1]].mark ^= 1;

        int temp = st[root].ls;
        st[root].ls = st[root].rs;
        st[root].rs = temp;

        temp = st[root].son[0];
        st[root].son[0] = st[root].son[1];
        st[root].son[1] = temp;
    }
}

void Updata(int root)
{
     st[root].ls = 0,st[root].rs = 0;

     if(st[root].son[0] != -1)
     {
         st[root].ls = st[st[root].son[0]].s;
     }

     if(st[root].son[1] != -1)
     {
         st[root].rs = st[st[root].son[1]].s;
     }

     st[root].s = st[root].ls + st[root].rs + 1;
}

void Init(int &root,int s,int e,int pre,char *S)
{
     if(s > e)
        return ;
     int mid = (s+e)>>1;
     root = Top++;
     st[root].son[0] = -1,st[root].son[1] = -1;
     st[root].pre = pre;
     st[root].data = http://www.mamicode.com/S[mid];>