思路
你很快能想到 ODT，然后，你会想到要维护一个存在的系统，那么你能想到平衡树，但是由于 FHQ 不支持乱序合并，平衡树用来解决区间问题，天然有左小右大，所以我们考虑用可莉线段树。
#include <iostream>
#include <map>using namespace std;const int MaxN = 1e5 + 10;struct S {int w, l, r;
} d[MaxN << 5];map<int, int> st;
int offline[MaxN << 5], rt[MaxN], b[MaxN], n, m, p, tot, cnt;int newnode() {return cnt ? offline[cnt--] : ++offline[0];
}void gooff(int k) {offline[++cnt] = k, d[k].l = d[k].r = d[k].w = 0;
}void modify(int &p, int k, int w, int l = 0, int r = n) {(p) || (p = newnode()), d[p].w += w;if (l == r) return;int mid = l + r >> 1;if (k <= mid) modify(d[p].l, k, w, l, mid);else modify(d[p].r, k, w, mid + 1, r);
}int query(int p, int pl, int pr, int l = 0, int r = n) {if (pl <= l && r <= pr) return d[p].w;if (pl > r || pr < l) return 0;int mid = l + r >> 1;return query(d[p].l, pl, pr, l, mid) + query(d[p].r, pl, pr, mid + 1, r);
}int merge(int p1, int p2) {if (!p1 || !p2) return p1 | p2;d[p1].w += d[p2].w, d[p1].l = merge(d[p1].l, d[p2].l), d[p1].r = merge(d[p1].r, d[p2].r); return gooff(p2), p1;
}void split(int x, int &y, int k) {if (!x) return;(y = newnode());if (d[d[x].l].w < k) split(d[x].r, d[y].r, k - d[d[x].l].w);else swap(d[x].r, d[y].r);if (k < d[d[x].l].w) split(d[x].l, d[y].l, k);d[y].w = d[x].w - k, d[x].w = k;
}int kth(int p, int k, int l = 0, int r = n) {if (l == r) return l;int mid = l + r >> 1;if (d[d[p].l].w >= k) return kth(d[p].l, k, l, mid);return kth(d[p].r, k - d[d[p].l].w, mid + 1, r);
}int length(auto it) {return (next(it) == st.end() ? n + 1 : next(it)->first) - it->first;
}int to(int k) {auto it = prev(st.upper_bound(k));return it->second == 1 ? kth(rt[it->first], length(it) - (p - it->first + 1) + 1) : kth(rt[it->first], p - it->first + 1);
}auto split(int p) {auto it = prev(st.upper_bound(p));if (it->first == p) return it;if (it->second) {swap(rt[it->first], rt[p]);split(rt[p], rt[it->first], length(it) - (p - it->first));} else {split(rt[it->first], rt[p], p - it->first);}return st.insert(it, make_pair(p, it->second));
}void assign(int l, int r, int c) {split(r + 1), split(l);for (auto it = st.find(l); it->first != r + 1; it = st.erase(it)) {if (l != it->first) rt[l] = merge(rt[l], rt[it->first]);}st[l] = c;
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> b[i]; st[i] = 0, modify(rt[i], b[i], 1);}for (int i = 1, op, l, r; i <= m; i++) {cin >> op >> l >> r;assign(l, r, op);}cin >> p;cout << to(p) << '\n';return 0;
}
跑的飞快 提交记录，直接占第四版，我还没卡常
另一种思路，考虑当一个序列有序时，将小于 val 的设为 0，否则为 1 若 pos 的值为 1，那么这个 val 还可以变大，所以我们考虑二分，对于操作我们发现已经变成了 01 序列，所以很容易进行一个相对的排序，具体的，可以通过区间修改 0/1 来实现