BZOJ1001【BJWC2017】神秘物质 < Splay >

Posted on 2018-08-20 Symbols count in article: 1.6k Reading time ≈ 6 mins.

Problem

【BJWC2017】神秘物质

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

$\mathrm{21ZZ}$ 年，冬。
小诚退休以后，不知为何重新燃起了对物理学的兴趣。他从研究所借了些实验仪器，整天研究各种微观粒子。
这一天，小诚刚从研究所得到了一块奇异的陨石样本，便迫不及待地开始观测。在精密仪器的视野下，构成陨石的每个原子都无比清晰。
小诚发现，这些原子排成若干列，每一列的结构具有高度相似性。于是，他决定对单独一列原子进行测量和测试。
被选中的这列共有 $N$ 个顺序排列的原子。最初，第 $i$ 个原子具有能量 $E_i$ 。随着时间推移和人为测试，这列原子在观测上会产生两种变化：

$merge\;x\;e$ ：当前第 $x$ 个原子和第 $x+1$ 个原子合并，得到能量为 $e$ 的新原子；
$insert\;x\;e$ ：在当前第 $x$ 个原子和第 $x+1$ 个原子之间插入一个能量为 $e$ 的新原子。

对于一列原子，小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值，称为区间极差。因此，除了观测变化外，小诚还要经常统计这列原子的两类数据：

$max\;x\;y$ ：当前第 $x$ 到第 $y$ 个原子之间的任意子区间中区间极差的最大值；
$min\;x\;y$ ：当前第 $x$ 到第 $y$ 个原子之间的任意子区间中区间极差的最小值。

其中，子区间指的是长度至少是 $2$ 的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿，你能否帮助他实现上述的观测和测量呢？

Input

第一行，两个整数 $N,M$ ，分别表示最初的原子数目和事件总数。
第二行， $N$ 个整数 $E_1,E_2,\cdots,E_N$ ，由空格隔开，依次表示每个原子的能量。
接下来 $M$ 行，每行为一个字符串和两个整数，描述一次事件，格式见题目描述。

Output

输出若干行，按顺序依次表示每次 $max$ 和 $min$ 类事件的测量结果。

Sample Input

4 3
5 8 10 2
max 1 3
min 1 3
max 2 4

Sample Output

5 2 8

HINT

$N,M\le10^5$ , $1\le e,E_i\le10^9$ 。
设 $N'$ 为当前时刻原子数目。
对于 $merge$ 类事件， $1\le x\le N'-1$ ；
对于 $insert$ 类事件， $1\le x\le N'$ ；
对于 $max$ 和 $min$ 类事件， $1\le x<y\le N'$ 。
任何时刻，保证 $N'\ge2$ 。

标签：Splay

Solution

$\mathrm{Splay}$ 基础题。

对于 $insert$ 操作，直接插入即可。
对于 $merge$ 操作，先删除第 $x$ 和 $x+1$ 个数，然后在第 $x-1$ 个数之后插入 $e$ 。
对于 $max$ 询问，易知其答案为该区间的最大数减最小数，于是在 $\mathrm{Splay}$ 上维护区间最大值和最小值即可。
对于 $min$ 询问，其答案一定存在于相邻两数的差之中，在 $\mathrm{Splay}$ 上维护区间相邻两数差的最小值。具体地，在第 $i$ 个数的位置维护第 $i$ 个数和第 $i+1$ 个数的差的绝对值，这样询问 $[l,r]$ 变为询问 $[l,r-1]$ 区间中差的最小值。注意在 $insert$ 和 $merge$ 时会导致插入位置相邻的数的差值发生变化，需要同时维护。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define INF 0x3f3f3f3f
#define flag cur->fa->fa!=tar&&cur->fa->fa->s[sn]==cur->fa
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
struct SplayNode {
    SplayNode *s[2], *fa; int sz, c, w, d, mi, mx;
    void update() {
        sz = (s[0]?s[0]->sz:0)+(s[1]?s[1]->sz:0)+1;
        d = min(min(w,(s[0]?s[0]->d:INF)),(s[1]?s[1]->d:INF));
        mi = min(min(c,(s[0]?s[0]->mi:INF)),(s[1]?s[1]->mi:INF));
        mx = max(max(c,(s[0]?s[0]->mx:-INF)),(s[1]?s[1]->mx:-INF));
    }
};
struct SplayTree {
    SplayNode* rt;
    SplayNode* newnode(int x, int y) {
        SplayNode* v = new SplayNode;
        v->s[0] = v->s[1] = v->fa = NULL;
        v->sz = 1, v->c = x, v->w = y;
        v->d = y, v->mi = v->mx = x;
        return v;
    }
    SplayTree() {
        rt = newnode(INF, INF);
        rt->s[1] = newnode(INF, INF);
        rt->mx = -INF, rt->s[1]->mx = -INF;
        rt->s[1]->fa = rt, rt->update();
    }
    void rotate(SplayNode* v, bool sn) {
        SplayNode* f = v->fa;
        f->s[sn^1] = v->s[sn], v->fa = f->fa;
        if (f->s[sn^1]) f->s[sn^1]->fa = f;
        if (v->fa) v->fa->s[f == f->fa->s[1]] = v;
        v->s[sn] = f, f->fa = v, f->update(), v->update();
    }
    void splay(SplayNode* cur, SplayNode* tar) {
        while (cur != tar && cur->fa != tar) {
            bool sn = cur->fa->s[1] == cur;
            if (flag) rotate(cur->fa, sn^1);
            rotate(cur, sn^1);
        }
        if (cur->fa == tar) rotate(cur, cur->fa->s[0] == cur);
        if (tar == rt) rt = cur;
    }
    SplayNode* get_kth(SplayNode* v, int k) {
        int lsz = v->s[0] ? v->s[0]->sz : 0;
        if (k <= lsz) return get_kth(v->s[0], k);
        if (k > lsz+1) return get_kth(v->s[1], k-lsz-1);
        return v;
    }
    void insert(int p, int x, int y) {
        SplayNode* pre = get_kth(rt, p);
        SplayNode* suc = get_kth(rt, p+1);
        splay(pre, rt), splay(suc, rt->s[1]);
        suc->s[0] = newnode(x, y), suc->s[0]->fa = suc;
        suc->update(), rt->update();
    }
    void remove(int p) {
        SplayNode* pre = get_kth(rt, p-1);
        SplayNode* suc = get_kth(rt, p+1);
        splay(pre, rt), splay(suc, rt->s[1]);
        suc->s[0]->fa = NULL, suc->s[0] = NULL;	
        suc->update(), rt->update();
    }
    int querymx(int l, int r) {
        SplayNode* pre = get_kth(rt, l-1);
        SplayNode* suc = get_kth(rt, r+1);
        splay(pre, rt), splay(suc, rt->s[1]);
        return suc->s[0]->mx-suc->s[0]->mi;
    }
    int querymi(int l, int r) {
        SplayNode* pre = get_kth(rt, l-1);
        SplayNode* suc = get_kth(rt, r+1);
        splay(pre, rt), splay(suc, rt->s[1]);
        return suc->s[0]->d;
    }
} BBST;
int n, m, a[MAX_N+5];
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n; i++)
        BBST.insert(i, a[i], (i<n?abs(a[i]-a[i+1]):INF));
    while (m--) {
        char opt[7]; scanf("%s", opt);
        if (opt[1] == 'e') {
            int p, x, y; read(p), read(x);
            BBST.remove(p+1), BBST.remove(p+1);
            SplayNode* pre = BBST.get_kth(BBST.rt, p);
            SplayNode* suc = BBST.get_kth(BBST.rt, p+1);
            if (p > 1) {
                int xx = pre->c, yy = abs(x-pre->c);
                BBST.remove(p), BBST.insert(p-1, xx, yy);
            }
            y = suc->c < INF ? abs(x-suc->c) : INF;
            BBST.insert(p, x, y);
        }
        if (opt[1] == 'n') {
            int p, x, y; read(p), read(x);
            SplayNode* pre = BBST.get_kth(BBST.rt, p+1);
            SplayNode* suc = BBST.get_kth(BBST.rt, p+2);
            int xx = pre->c, yy = abs(x-pre->c);
            BBST.remove(p+1), BBST.insert(p, xx, yy);
            y = suc->c < INF ? abs(x-suc->c) : INF;
            BBST.insert(p+1, x, y);
        }
        if (opt[1] == 'a') {
            int l, r; read(l), read(r);
            printf("%d\n", BBST.querymx(l+1, r+1));
        }
        if (opt[1] == 'i') {
            int l, r; read(l), read(r);
            printf("%d\n", BBST.querymi(l+1, r));
        }
    }
    return 0;
}