我的思路就是：

把两种询问的答案分别放进可删堆里面，每一次插入的时候就更新两种可删堆。只有 MIN_SORT_GAP 询问要用平衡树，我猜测大概率是这种询问有问题。

WA 14，只有 Test 1 对了。

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

struct heap_can_delete {
	priority_queue<int,vector<int>,greater<int> > A, B;
	void ins(int x) {
		A.push(x);
	}
	void del(int x) {
		B.push(x);
	}
	int query() {
		while (!B.empty() && A.top() == B.top()) {
			A.pop();
			B.pop();
		}
		return A.top();
	}
} H1, H2;
int n;
int a[1000005];

struct FHQ_treap {
	struct node {
		int val, pty, sz;
		int ls, rs;
	} t[2000005];
	int cnt = 0, root = 0;
	void pushup(int x) {
		t[x].sz = t[t[x].ls].sz + 1 + t[t[x].rs].sz;
	}
	int newnode(int val) {
		cnt++;
		t[cnt].sz = 1;
		t[cnt].val = val;
		t[cnt].pty = rand();
		return cnt;
	}
	int merge(int x,int y){
		if(!x||!y){
			return x+y;
		}
		if(t[x].pty<t[y].pty){
			t[x].rs=merge(t[x].rs,y);
			pushup(x);
			return x;
		}
		else{
			t[y].ls=merge(x,t[y].ls);
			pushup(y);
			return y;
		}
	}
	void split(int now, int k, int &x, int &y) {
		if (!now) {
			x = 0;
			y = 0;
		} else if (t[now].val <= k) {
			x = now;
			split(t[now].rs, k, t[now].rs, y);
			pushup(now);
		} else {
			y = now;
			split(t[now].ls, k, x, t[now].ls);
			pushup(now);
		}
	}

	int kth(int now, int k) {
		while (1) {
			if (k <= t[t[now].ls].sz) {
				now = t[now].ls;
			} else if (k == t[t[now].ls].sz + 1) {
				return now;
			} else {
				k -= t[t[now].ls].sz + 1;
				now = t[now].rs;
			}
		}
	}

	void ins(int val, int x, int y) {
		split(root, val, x, y);
		int newval = newnode(val);
		int tmp = merge(x, newval);
		root = merge(tmp, y);
	}

	void dlt(int val, int x, int y, int z) {
		split(root, val, x, z);
		split(x, val - 1, x, y);
		y = merge(t[y].ls, t[y].rs);
		int w = merge(x, y);
		root = merge(w, z);
	}

	int rnk(int val, int x, int y) {
		split(root, val - 1, x, y);
		int res = t[x].sz + 1;
		root = merge(x, y);
		return res;
	}

	int num(int val) {
		return t[kth(root, val)].val;
	}
	int pre(int val,int x,int y){
		split(root,val-1,x,y);
		int res=t[kth(x,t[x].sz)].val;
		root=merge(x,y);
		return res;
	}
	int suf(int val,int x,int y){
		split(root,val,x,y);
		int res=t[kth(y,1)].val;
		root=merge(x,y);
		return res;
	}
} Treap;
int elecnt = 0;
int fl1 = 0;

signed main() {
	int n, m;
	cin >> n >> m;
	int X, Y, Z, W;
	Treap.ins(-1e9, X, Y);
	Treap.ins(1e9, X, Y);
	elecnt = 2;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (fl1==0) {
			int cntsame = Treap.rnk(Treap.suf(a[i], X, Y), Z, W) - Treap.rnk(Treap.pre(a[i], X, Y), Z, W) - 1;
//			cout<<cntsame<<"\n";
			if (cntsame >= 1) {
				fl1 = 1;
			} else {
				Treap.ins(a[i], X, Y);
				elecnt++;
			}
		}
		if (i != 1) {
			H1.ins(max(a[i], a[i - 1]) - min(a[i], a[i - 1]));
//			cout<<"push "<<max(a[i], a[i - 1]) - min(a[i], a[i - 1])<<"\n";
		}
	}
	for (int i = 1; i <= n; i++) {
		if (fl1==0) {
			int tmp = Treap.pre(a[i], X, Y);
			H2.ins(a[i] - tmp);
		}
	}
//	cout << H2.query() << "\n";
	while (m--) {
		string op;
		cin >> op;
		if (op == "INSERT") {
			int x, y;
			cin >> x >> y;
			if (x != n) {
				H1.del(max(a[x], a[x + 1]) - min(a[x], a[x + 1]));
//				cout<<"pop "<<max(a[x], a[x + 1]) - min(a[x], a[x + 1])<<"\n";
				H1.ins(max(a[x + 1], y) - min(a[x + 1], y));
//				cout<<"push "<<max(a[x + 1], y) - min(a[x + 1], y)<<"\n";
			}
			H1.ins(max(a[x], y) - min(a[x], y));
//			cout<<"push "<<max(a[x], y) - min(a[x], y)<<"\n";
			a[x]=y;
			if (fl1==0) {
				int cntsame = Treap.rnk(Treap.suf(y, X, Y), Z, W) - Treap.rnk(Treap.pre(y, X, Y), Z, W) - 1;
				if (cntsame >= 1) {
					fl1 = 0;
				} else {
					Treap.ins(y, X, Y);
					elecnt++;
					int tmp = Treap.pre(y, X, Y);
					int tmp2 = Treap.suf(y, X, Y);
					H2.ins(y - tmp);
					H2.ins(tmp2 - y);
				}
			}
		}
		if (op == "MIN_GAP") {
			cout << H1.query() << "\n";
		}
		if (op == "MIN_SORT_GAP") {
			if (fl1) {
				cout << 0 << "\n";
			} else {
				cout << H2.query() << "\n";
			}
		}
	}
	return 0;
}