写这个题跟用户名没啥关系。
设 \(a_i=0\) 的位置为 \(c_1,\cdots,c_m\)，\(pre_i\) 为 \(a_{1\sim i}\) 中 \(0\) 的个数。可以发现 \(b_{c_i}\) 是严格单调递增的，设其中的数值构成的集合为 \(S\)。
从值域考虑，不难发现对于非 \(0\) 的 \(a_i=v\)，我们只关心其第一次出现的位置 \(p_v\)，设 \(d_v=pre_{p_v}\)（若没有出现 \(v\) 则 \(d_v=m\)）。按值域从小到大枚举 \(v=1\sim n\)，设 \(s_v\) 为 \(1\sim v-1\) 中 \(\notin S\) 的数的个数，则
查询 \(a_y\) 时，若 \(a_y=0\)，则相当于查询第 \(pre_y\) 小的 \(S\) 中的数。在值域上开一棵线段树，区间内维护 \(v-d_v-s_v\leq 0\) 的数的个数，线段树二分即可得到结果。
考虑如何处理修改。每次将 \(a_x\) 修改为 \(a_x'\) 后，\(d_{a_x}\) 和 \(d_{a_x'}\) 都可能变化。这相当于做两次对 \(v-d_v-s_v\) 的单点修改。考察某次单点修改带来的变化，若原先 \(v-d_v-s_v>0\)，修改后 \(v-d_v-s_v\leq 0\)，则 \(v\) 插入 \(S\) 中，\(v+1\sim n\) 中的值的 \(s_v\) 都会减 \(1\)。注意到，这可能导致 \(v+1\sim n\) 中的某些值的 \(v-d_v-s_v\) 从 \(\leq 0\) 变成 \(>0\)，此时我们取最小的这样的数 \(v_{\min}\)，则 \(v_{\min}\) 将从 \(S\) 中删除，删除后更大的值就恢复正常了。另一种情况也是对称的。
同样用线段树维护，区间内维护 \(\in S\) 的值的最大值及其位置，和 \(\notin S\) 的值的最小值及其位置，还有加法标记即可。\(p_v\) 可以用 set 或者懒删除的堆维护。时间复杂度为 \(\mathcal{O}((n+q)\log{n})\)。
主要代码
int n, q, a[MAXN], pre[MAXN], val[MAXN];
bool vis[MAXN];
priority_queue<int, vector<int>, greater<>> Q[MAXN];struct SegTree {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)struct Node {int mn, mnp, mx, mxp, cnt;Node &operator+=(const Node &rhs) {if (rhs.mn < mn) {mn = rhs.mn;mnp = rhs.mnp;}if (rhs.mx > mx) {mx = rhs.mx;mxp = rhs.mxp;}cnt += rhs.cnt;return *this;}friend Node operator+(Node lhs, const Node &rhs) {return lhs += rhs;}} nd[MAXN << 2];int tg[MAXN << 2];void build(int p, int l, int r) {if (l == r) {nd[p] = {inf, 0, -inf, 0, 0};if (val[l] > 0) {vis[l] = false;nd[p].mn = val[l];nd[p].mnp = l;} else {vis[l] = true;nd[p].mx = val[l];nd[p].mxp = l;nd[p].cnt = 1;}return;}int mid = l + r >> 1;build(ls(p), l, mid);build(rs(p), mid + 1, r);pushUp(p);}void pushUp(int p) {nd[p] = nd[ls(p)] + nd[rs(p)];}void applyAdd(int p, int v) {tg[p] += v;if (nd[p].mn != inf) nd[p].mn += v;if (nd[p].mx != -inf) nd[p].mx += v;}void pushDown(int p) {if (!tg[p]) return;applyAdd(ls(p), tg[p]);applyAdd(rs(p), tg[p]);tg[p] = 0;}int query(int p, int l, int r, int x) {if (l == r) return vis[l] ? nd[p].mx : nd[p].mn;pushDown(p);int mid = l + r >> 1;return x <= mid ? query(ls(p), l, mid, x) : query(rs(p), mid + 1, r, x);}void upd(int p, int l, int r, int x) {if (l == r) {if (nd[p].mn <= 0) {nd[p].mx = nd[p].mn;nd[p].mn = inf;swap(nd[p].mnp, nd[p].mxp);} else if (nd[p].mx > 0) {nd[p].mn = nd[p].mx;nd[p].mx = -inf;swap(nd[p].mnp, nd[p].mxp);}nd[p].cnt = vis[l];return;}pushDown(p);int mid = l + r >> 1;if (x <= mid) upd(ls(p), l, mid, x);else upd(rs(p), mid + 1, r, x);pushUp(p);}void add(int p, int l, int r, int x, int y, int v) {if (x <= l && y >= r) {applyAdd(p, v);return;}pushDown(p);int mid = l + r >> 1;if (x <= mid) add(ls(p), l, mid, x, y, v);if (y > mid) add(rs(p), mid + 1, r, x, y, v);pushUp(p);}int find(int p, int l, int r, int k) {if (l == r) return l;pushDown(p);int mid = l + r >> 1;return k <= nd[ls(p)].cnt ? find(ls(p), l, mid, k) : find(rs(p), mid + 1, r, k - nd[ls(p)].cnt);}
#undef ls
#undef rs
} sgt;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> q;for (int i = 1; i <= n; ++i) {cin >> a[i];pre[i] = pre[i - 1] + (a[i] == 0);}int m = pre[n];for (int v = 1, cnt = 0; v <= n; ++v) {val[v] = v - m - cnt;if (val[v] > 0) ++cnt;}sgt.build(1, 1, n);while (q--) {int x, k, y;cin >> x >> k >> y;auto getD = [&](int v) {if (v <= 0) return -1;while (!Q[v].empty() && a[Q[v].top()] != v) Q[v].pop();return Q[v].empty() ? m : pre[Q[v].top()];};auto upd = [&](int v, int dt) {int prvVal = sgt.query(1, 1, n, v), nxtVal = prvVal + dt;sgt.add(1, 1, n, v, v, dt);if (prvVal > 0 && nxtVal <= 0) {vis[v] = true;sgt.upd(1, 1, n, v);if (v < n) {sgt.add(1, 1, n, v + 1, n, 1);if (sgt.nd[1].mx > 0) {int p = sgt.nd[1].mxp;vis[p] = false;sgt.upd(1, 1, n, p);if (p < n) sgt.add(1, 1, n, p + 1, n, -1);}}} else if (prvVal <= 0 && nxtVal > 0) {vis[v] = false;sgt.upd(1, 1, n, v);if (v < n) {sgt.add(1, 1, n, v + 1, n, -1);if (sgt.nd[1].mn <= 0) {int p = sgt.nd[1].mnp;vis[p] = true;sgt.upd(1, 1, n, p);if (p < n) sgt.add(1, 1, n, p + 1, n, 1);}}}};int tmp = a[x], prv1 = getD(tmp), prv2 = getD(k);a[x] = k;if (k > 0) Q[k].emplace(x);int nxt1 = getD(tmp), nxt2 = getD(k);if (tmp > 0) upd(tmp, prv1 - nxt1);if (k > 0) upd(k, prv2 - nxt2);cout << (a[y] ? a[y] : sgt.find(1, 1, n, pre[y])) << '\n';}return 0;
}