传送门
题意
先给定一个初始长度为n的初始数组，要求实现3个操作：
1.INSERT i k：在原数列的第 i 个元素后面添加一个新元素 k；如果原数列的第 i 个元素已经添加了若干元素，则添加在这些元素的最后（见样例说明）。
2.MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值。
3.MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）。
分析
1.第3个操作需要用到平衡树，在每次插入一个数的时候找到其前驱&后继，统计全剧最小值即为答案。
2.第2个操作，插入一个数的时候会破坏一个相邻关系，新增两个相邻关系。我们可以用一个可删除元素的堆来维护每对相邻元素的差的绝对值。
3.第1个操作，插入&读入原数列的时候，就只要维护在原数列的第 i 个元素的“尾巴”上的元素(r数组)是什么就行了。还要在平衡树中insert这个数。
这里我们拿multiset作为可删除元素的堆，splay作为平衡树（查找前驱后继）
注意：multiset中erase(val)函数会删除所有值为val的节点，如果要只删除一个，应该写成：
S.erase(S.find(val));
代码
#include <bits/stdc++.h>using namespace std;
//-----pre_def----
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
#define init_h memset(h, -1, sizeof h), idx = 0;
#define lowbit(x) x &(-x)//---------------
const int N = 1e6 + 10;
int n, m;
int r[N], d[N];
int ans3 = INF;
multiset<int> S;
struct node
{
int s[2], p, v; //s[0]==lson,s[1]==rson,p=pre,v=val（注意：splay中的val不作为排序依据，只在初始状态下有序）int size; //size==包括自身在内的子树的节点数//int lz;//懒标记，可以记录翻转信息void init(int _v, int _p){
v = _v;p = _p;size = 1;}
} tr[N];
int root, idx;
void pushup(int u); //由子向父更新
//void pushdown(int u);//区间翻转时的向下更新
void rotate(int x); //核心函数1：将所有情况的左旋右旋写在一个函数里面
void splay(int x, int k); //核心函数2：将x节点旋转至k下面,如果k是0则旋转到根
int find(int v); //查找v的位置，并将其旋转到根节点
int insert(int v); //插入v
void del(int v); //删除值为v
void del(int l, int r); //删除值为(l~r)的所有点
int find_pre(int v); //查找v的前驱的节点编号
int find_ne(int v); //查找v的后继的节点编号
int get(int v); //查找值等于v的点的编号；如果不存在值为v的点，则输出大于v的最小值所在的点的编号
int find_k(int k); //查找排名为k(中序遍历第k个)的数
void pushup(int u)
{
tr[u].size = tr[tr[u].s[0]].size + tr[tr[u].s[1]].size + 1;
}
// void pushdown(int u)
// {
// if (tr[u].lz)
// {
// if (tr[u].lz)
// {
// swap(tr[u].s[1], tr[u].s[0]);
// tr[tr[u].s[0]].lz ^= 1;
// tr[tr[u].s[1]].lz ^= 1;
// tr[u].lz = 0;
// }
// }
// }
void rotate(int x) //核心函数1：将所有情况的左旋右旋写在一个函数里面
{
int y = tr[x].p, z = tr[y].p; //在这个链上：z是祖宗，y是爸爸，x是儿子。现在要把x移动到最上边int k = tr[y].s[1] == x; // k=0表示x是y的左儿子；k=1表示x是y的右儿子tr[z].s[tr[z].s[1] == y] = x;tr[x].p = z;tr[y].s[k] = tr[x].s[k ^ 1];tr[tr[x].s[k ^ 1]].p = y;tr[x].s[k ^ 1] = y;tr[y].p = x;pushup(y), pushup(x); //顺序不能乱
}
void splay(int x, int k) //核心函数2：将x节点旋转至k下面,如果k是0则旋转到根
{
while (tr[x].p != k) //但x的父节点不为k时{
int y = tr[x].p, z = tr[y].p;if (z != k) //x的祖宗还不是k{
if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) //异或，当zyx不为一条直链的时候{
rotate(x);}else{
rotate(y);}}rotate(x);}if (!k) //如果k==0，等加于将x旋转至rootroot = x;
}
int find(int v) //查找v的位置，并将其旋转到根节点(此时左子树的size就是v的排名)
{
int u = root;if (!u)return -1; //树空while (tr[u].s[v > tr[u].v] && v != tr[u].v) //当存在儿子并且当前位置的值不等于xu = tr[u].s[v > tr[u].v]; //跳转到儿子，查找x的父节点splay(u, 0); //把当前位置旋转到根节点return root;
}
int insert(int v) //插入一个数,并返回节点编号
{
int u = root, p = 0;while (u) //找到应该要插入的位置{
p = u, u = tr[u].s[v > tr[u].v];}u = ++idx;if (p)tr[p].s[v > tr[p].v] = u;tr[u].init(v, p);splay(u, 0);return u;
}
void del(int v) //删除值为v的点
{
int last = find_pre(v); //查找x的前驱int next = find_ne(v); //查找x的后继splay(last, 0);splay(next, last);//将前驱旋转到根节点，后继旋转到根节点下面//很明显，此时后继是前驱的右儿子，x是后继的左儿子，并且x是叶子节点int del = tr[next].s[0]; //后继的左儿子tr[next].s[0] = 0; //这个节点直接丢掉（不存在了）
}
void del(int l, int r) //删除值为(l~r)的所有点
{
int last = get(l); //查找x的前驱int next = get(r); //查找x的后继splay(next, 0);splay(last, next);tr[last].s[1] = 0; //这个节点直接丢掉（不存在了）pushup(last), pushup(next);
}
int find_pre(int v) //查找v的前驱的节点编号
{
find(v);int u = root; //根节点，此时x的父节点（存在的话）就是根节点if (tr[u].v < v)return u; //如果当前节点的值小于x并且要查找的是前驱u = tr[u].s[0]; //查找后继的话在右儿子上找，前驱在左儿子上找while (tr[u].s[1])u = tr[u].s[1]; //要反着跳转，否则会越来越大（越来越小）return u; //返回位置
}
int find_ne(int v) //查找v的后继的节点编号
{
find(v);int u = root; //根节点，此时x的父节点（存在的话）就是根节点if (tr[u].v > v)return u; //如果当前节点的值小于x并且要查找的是前驱u = tr[u].s[1]; //查找后继的话在右儿子上找，前驱在左儿子上找while (tr[u].s[0])u = tr[u].s[0]; //要反着跳转，否则会越来越大（越来越小）return u; //返回位置
}
int get(int v) //查找值等于v的点的编号；如果不存在值为v的点，则输出大于v的最小值所在的点的编号
{
int u = root, res;while (u){
if (tr[u].v >= v)res = u, u = tr[u].s[0];elseu = tr[u].s[1];}return res;
}
int find_k(int k) //查找排名为k的数
{
int u = root;while (u){
if (tr[tr[u].s[0]].size >= k)u = tr[u].s[0];else if (tr[tr[u].s[0]].size + 1 == k)return tr[u].v;elsek -= tr[tr[u].s[0]].size + 1, u = tr[u].s[1];}return -1;
}void print(int u) //输出中序遍历，debug用
{
if (tr[u].s[0])print(tr[u].s[0]);printf("%d ", tr[u].v);if (tr[u].s[1])print(tr[u].s[1]);
}
void debug()
{
cout << "----------------" << endl;print(root);puts("");cout << ans3 << endl;for (auto item : S){
cout << -item << endl;}cout << "----------------" << endl;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);int StartTime = clock();
#endifscanf("%d%d", &n, &m);d[0] = INF;d[n + 1] = INF;insert(-INF), insert(INF);fir(i, 1, n){
scanf("%d", &d[i]);r[i] = d[i];S.insert(abs(d[i] - d[i - 1]));insert(d[i]);ans3 = min(ans3, min(abs(tr[find_pre(d[i])].v - d[i]), abs(tr[find_ne(d[i])].v - d[i])));}//debug();while (m--){
char op[10];int i, k;scanf("%s", op);if (!strcmp(op, "INSERT")){
scanf("%d%d", &i, &k);S.erase(S.find(abs(r[i] - d[i + 1])));S.insert(abs(k - d[i + 1]));S.insert(abs(r[i] - k));r[i] = k;insert(k);ans3 = min(ans3, min(abs(tr[find_pre(k)].v - k), abs(tr[find_ne(k)].v - k)));//debug();}else if (!strcmp(op, "MIN_GAP")){
printf("%d\n", *S.begin());}else{
printf("%d\n", ans3);}}
#ifndef ONLINE_JUDGEprintf("Run_Time = %d ms\n", clock() - StartTime);
#endifreturn 0;
}