Splay Tree 支持的之中操作。

插入，删除，求前驱和后即，区间更新与查询。

先来一发Splay Tree最基础的操作——伸展，顺便求前驱和后即。[HNOI2002]营业额统计。

白书上讲的貌似要讨论目标节点，父节点，父节点的父节点，这三个节点之间的关系。

没太看懂，直接按照自己想得来了。

#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 LL
#define _LL __int64
#define _INF 0x3f3f3f3f
#define Mod 1000000007

using namespace std;

const int MAXN = 100100;

struct N
{
    int data,son[2],pre;
}st[MAXN*2];

int Top;

void Rotate(int root,int pre,int dir)
{
    N temp = st[pre];
    temp.son[dir] = st[root].son[!dir];
    st[pre] = st[root];
    st[pre].son[!dir] = root;
    st[root] = temp;

    st[pre].pre = temp.pre;

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


//将目标节点旋转到goal下面，若goal == -1,则表示为将目标节点旋转到根节点。
void Splay(int root,int goal)
{
    while(st[root].pre != goal)
    {
        Rotate(root,st[root].pre,st[st[root].pre].son[0] == root ? 0 : 1);
        root = st[root].pre;
    }
}

bool Insert(int &root,int x,int pre)
{
    if(root == -1 || st[root].data =http://www.mamicode.com/= -1)>