代码：

#include <bits/stdc++.h>
#define N 600005
using namespace std;
struct node {
	int head, tail;
} a[N];
struct tt {
	struct treap {
		int l, r, size, val, pri;
	} t[N];
	int cnt, rt;
	
	int create(int v) {
		t[++cnt].val = v;
		t[cnt].pri = rand();
		t[cnt].size = 1;
		return cnt;
	}
	void update(int p) {
		t[p].size = t[t[p].l].size + t[t[p].r].size + 1;
	}
	void split(int p, int v, int &x, int &y) {
		if (!p) {
			x = y = 0;
			return ;
		}
		if (t[p].val <= v) {
			x = p;
			split(t[p].r, v, t[p].r, y);
		} else {
			y = p;
			split(t[p].l, v, x, t[p].l);
		}
		update(p);
	}
	int merge(int x, int y) {
		if (!x || !y)
			return max(x, y);
		if (t[x].pri < t[y].pri) {
			t[x].r = merge(t[x].r, y);
			update(x);
			return x;
		} else {
			t[y].l = merge(x, t[y].l);
			update(y);
			return y;
		}
	}
	void insertt(int v) {
		int x, y;
		split(rt, v, x, y);
		rt = merge(merge(x, create(v)), y);
	}
	void delt(int v) {
		int x, y, z;
		split(rt, v, x, y);
		split(x, v - 1, x, z);
		z = merge(t[z].l, t[z].r);
		rt = merge(merge(x, z), y);
	}
	int kth(int p, int k) {
		while (1) {
			if (k <= t[t[p].l].size)
				p = t[p].l;
			else if (k == t[t[p].l].size + 1)
				return p;
			else {
				k -= t[t[p].l].size + 1;
				p = t[p].r;
			}
		}
	}
	int nextt(int v) {
		int x, y;
		split(rt, v - 1, x, y);
		if (y == 0) {
			rt = merge(x, y); 
			return -1;
		}
		int ans = t[kth(y, 1)].val;
		rt = merge(x, y);
		return ans;
	}
	int pret(int v) {
		int x, y;
		split(rt, v, x, y);
		if (x == 0) {
			rt = merge(x, y);
			return -1;
		}
		int ans = t[kth(x, t[x].size)].val;
		rt = merge(x, y);
		return ans;
	}
};
tt t1, t2;
signed main() {
	int n, m, ans2 = 1e9;
	string s;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i].head);
		a[i].tail = a[i].head;
		if (i != 1)
			t2.insertt(abs(a[i].head - a[i - 1].tail));
		//cout << "!!! " << t2.kth(t2.rt, 1) << '\n';
		int pre = t1.pret(a[i].head), nxt = t1.nextt(a[i].head);
		if (pre != -1)
			ans2 = min(ans2, a[i].head - pre);
		if (nxt != -1)
			ans2 = min(ans2, nxt - a[i].head);
		t1.insertt(a[i].head);
	}
	int i, k;
	while (m--) {
		cin >> s;
		if (s == "INSERT") {
			scanf("%d%d", &i, &k);
			if (i < n) {
				t2.delt(abs(a[i].tail - a[i + 1].head));
				t2.insertt(abs(a[i + 1].head - k));
			}
			t2.insertt(abs(a[i].tail - k));
			//cout << k << ' ' << a[i].tail << ' ' << a[i + 1].head << ' ' << abs(a[i].tail - a[i + 1].head) << ' ' << abs(a[i + 1].head - k) << ' ' << abs(a[i].tail - k) << '\n';
			a[i].tail = k;
			int pre = t1.pret(k), nxt = t1.nextt(k);
			if (pre != -1)
				ans2 = min(ans2, k - pre);
			if (nxt != -1)
				ans2 = min(ans2, nxt - k);
			t1.insertt(k);
		} else if (s == "MIN_GAP") {
			printf("%d\n", t2.t[t2.kth(t2.rt, 1)].val);
		} else {
			printf("%d\n", ans2);
		}
	}
	return 0;
}

不知道是不是常数问题，dalao们是怎样优化的呀？