4864: [BeiJing 2017 Wc]神秘物质

题意：

给你一个序列，有插入、删除操作，询问区间极差最大最小值。

题解：

md智商下线。。还想着差分然后最大子段和。。。
极差最大就是区间最大值减最小值，极差最小一定在相邻两个数之间，用序列之王splay搞一下就好了。

代码：

#include <bits/stdc++.h>
using namespace std;

const int inf = 2147483647;
int n, m, e[100010];
struct pnt
{
    pnt *f, *s[2];
    int x, sz, ori, mxori, mnori, mnx;
    pnt(int ori, int x) : x(x), ori(ori), sz(1), s(), mxori(ori), mnori(ori), mnx(abs(x)) {}
} *root;

void pushup(pnt *x)
{
    x->mxori = max(x->s[0] ? x->s[0]->mxori : 0, max(x->ori, x->s[1] ? x->s[1]->mxori : 0));
    x->mnori = min(x->s[0] ? x->s[0]->mnori : inf, min(x->ori, x->s[1] ? x->s[1]->mnori : inf));
    x->mnx = min(x->s[0] ? x->s[0]->mnx : inf, min(abs(x->x), x->s[1] ? x->s[1]->mnx : inf));
    x->sz = (x->s[0] ? x->s[0]->sz : 0) + 1 + (x->s[1] ? x->s[1]->sz : 0);
}
void rot(pnt *x)
{
    pnt *f = x->f, *ff = f->f;
    int w = x == f->s[0];
    f->s[1 - w] = x->s[w];
    if (x->s[w]) x->s[w]->f = f;
    if (ff) ff->s[f == ff->s[1]] = x;
    x->f = ff;
    x->s[w] = f;
    f->f = x;
    pushup(f);
    pushup(x);
}
void splay(pnt *x, pnt *rt)
{
    while (x->f != rt)
    {
        pnt *f = x->f, *ff = f->f;
        if (ff == rt) rot(x);
        else if ((ff->s[0] == f) == (f->s[0] == x)) rot(f), rot(x);
        else rot(x), rot(x);
    }
    if (rt == NULL) root = x;
}
pnt *get_k(int k)
{
    pnt *now = root;
    while (1)
    {
        int lsz = now->s[0] ? now->s[0]->sz : 0;
        if (k <= lsz) now = now->s[0];
        else if (k == lsz + 1) return now;
        else now = now->s[1], k -= lsz + 1;
    }
    assert(0);
}
int get_mn(int l, int r)
{
    l--, r++;
    splay(get_k(l), 0);
    splay(get_k(r), root);
    return root->s[1]->s[0]->mnx;
}
int get_mx(int l, int r)
{
    l--, r++;
    splay(get_k(l), 0);
    splay(get_k(r), root);
    return root->s[1]->s[0]->mxori - root->s[1]->s[0]->mnori;
}
void insert(int k, int ori)
{
    splay(get_k(k), 0);
    pnt *now = root;
    now = now->s[1];
    while (now->s[0]) now = now->s[0];
    splay(now, root);
    now->s[0] = new pnt(ori, ori - root->ori);
    now->s[0]->f = now;
    now->x = now->ori - now->s[0]->ori;
    now->mnx = abs(now->x);
    splay(now->s[0], 0);
}
void merge(int k, int ori)
{
    splay(get_k(k - 1), 0);
    splay(get_k(k + 2), root);
    if (root->s[1]->s[0]->s[0]) rot(root->s[1]->s[0]->s[0]);
    pnt *now = root->s[1]->s[0];
    now->ori = ori;
    now->x = now->ori - root->ori;
    now->mxori = now->mnori = now->ori;
    now->mnx = abs(now->x);
    delete now->s[1];
    now->s[1] = NULL;
    root->s[1]->x = root->s[1]->ori - now->ori;
    root->s[1]->mnx = abs(root->s[1]->x);
    splay(now, 0);
}
void print(pnt *x)
{
    if (!x) return;
    printf("i: %x f: %x s[0]: %x s[1]: %x x: %d sz: %d ori: %d mxori: %d mnori: %d mnx: %d\n", x, x->f, x->s[0], x->s[1], x->x, x->sz, x->ori, x->mxori, x->mnori, x->mnx);
    print(x->s[0]);
    print(x->s[1]);
}
int main()
{
    scanf("%d%d", &n, &m);
    root = new pnt(0, 0);
    root->f = NULL;
    root->s[0] = new pnt(0, 0);
    root->s[0]->f = root;
    pushup(root);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &e[i]);
        insert(i, e[i]);
    }
    // print(root);
    for (int i = 0; i < m; i++)
    {
        char op[9];
        scanf("%s", op);
        if (op[1] == 'e')
        {
            int x, e;
            scanf("%d%d", &x, &e);
            merge(x + 1, e);
        }
        else if (op[1] == 'n')
        {
            int x, e;
            scanf("%d%d", &x, &e);
            insert(x + 1, e);
        }
        else
        {
            int x, y;
            scanf("%d%d", &x, &y);
            if (op[1] == 'i') printf("%d\n", get_mn(x + 2, y + 1));
            else printf("%d\n", get_mx(x + 1, y + 1));
        }
        // print(root);
    }
}