我们考察将原序列排序、去重后的差分，那么一轮游戏相当于全局 $-1$ 并删去所有 $0$。$k$ 轮之后所有 $\le k$ 的差分全部都会被删去，于是可以二分算出被删除的元素个数。至此第一问解决。

对于第二问，我们先假装所有人的级别都不一样，那么过一轮会多 $n(n-1)/2$ 的经验。每删去一个 $0$，都会导致一个前缀的贡献 $-1$。假设 $i$ 处的 $0$ 在 $t_i$ 时刻被删去了，那么其会贡献 $-i(k-t_i)=t_i\times i-k\times i$。发现这个时刻其实就是差分值，还是一样二分找到上一个有数被删的时刻，前缀和维护即可。

第三问将问题聚焦到了某个人 $p$ 上。仿照第二问，先假装这个人加的经验一直不变。我们现在只关心排序后满足位置 $i$ 在 $p$ 之后且删除时间 $t_i$ 在 $k$ 之前的贡献，这个贡献为 $t_i-k$。这是一个二维偏序问题，离线在 $k$ 这维做扫描线即可。

总时间复杂度 $\mathcal{O}(n\log n)$。注意运算过程可能爆 long long。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef __int128 lll;

const int MAXN = 3e5 + 10;

struct query {
	ll k; int p, id;
	query(ll k = 0, int p = 0, int id = 0) : k(k), p(p), id(id) {}
	bool operator < (const query &rhs) const { return k < rhs.k; }
} q[MAXN]; int tot;

int n, m; ll cv[MAXN], cp[MAXN];

inline 
void add(int k, ll x) {
	for (int i = k; i; i &= i - 1) cv[i] += x, cp[i]++; 
}

inline 
ll ask(int k, ll x) {
	ll res = (n - k) * x;
	for (int i = k; i <= n; i += i & -i) res += cv[i] - x * cp[i];
	return res;
}

struct node {
	ll val; int id;
	node(ll val = 0, int id = 0) : val(val), id(id) {}
	bool operator < (const node &rhs) const { return val < rhs.val; }
} s[MAXN]; ll sv[MAXN], sp[MAXN];

int rk[MAXN], tmp[MAXN], op, p; ll k, ans[MAXN], a[MAXN], b[MAXN];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i];
	for (int i = 1; i <= n; i++) tmp[i] = i;
	sort(tmp + 1, tmp + n + 1, [](int i, int j) { return a[i] < a[j]; });
	for (int i = 1; i <= n; i++) rk[tmp[i]] = i;
	sort(b + 1, b + n + 1);
	for (int i = 1; i < n; i++) b[i] = b[i + 1] - b[i];
	for (int i = 1; i < n; i++) s[i] = node(b[i], i);
	sort(b + 1, b + n), sort(s + 1, s + n);
	for (int i = 1; i < n; i++) sv[i] = sv[i - 1] + (ll)s[i].val * s[i].id;
	for (int i = 1; i < n; i++) sp[i] = sp[i - 1] + s[i].id;
	for (int i = 1; i <= m; i++) {
		scanf("%d%lld", &op, &k);
		if (op == 1) ans[i] = n - (upper_bound(b + 1, b + n, k) - b - 1);
		else if (op == 2) {
			int t = lower_bound(b + 1, b + n, k) - b - 1;
			ans[i] = (lll)n * (n - 1) / 2 * k + sv[t] - (lll)k * sp[t];
		} else scanf("%d", &p), q[++tot] = query(k, p, i);
	}
	sort(q + 1, q + tot + 1);
	for (int i = 1, j = 1; i <= tot; i++) {
		for (; j < n && s[j].val < q[i].k; add(s[j].id, s[j].val), j++);
		ans[q[i].id] = a[q[i].p] + ask(rk[q[i].p], q[i].k);
	}
	for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
}