终于入门整体二分了，勉勉强强算是搞懂了一个题目吧。
整体二分很多时候可以比较好的离线处理区间\(K\)大值的相关问题。考虑算法流程：
操作队列\(arr\)，其中有询问和修改两类操作。
每次在答案的可行值域上二分一个\(mid\)，把询问的答案\(>mid\)的分在\(R\)部，\(<=mid\)的分在\(L\)部。把修改的值\(>mid\)的分在\(R\)部，\(<=mid\)的分在\(L\)部。
何谓整体二分？就是直接一起二分所有的询问操作的答案，然后暴力扫描当前操作区间，将其划分为答案的左子区间与右子区间两个部分。
那么以什么为划分依据呢？看看这个操作对于左子区间有没有贡献。如果没有，那么就划分到右子区间中，然后将这个操作的权值更改为这个贡献减去所需的贡献，反之，则划分到左子区间中，同时将这个操作的贡献加入某一个容器，为询问操作服务。
这么说可能有点晕。就这道题说的话，应该是这样：
我们设尚未解决的操作区间为\([ql,qr]\),答案区间为[l,r][l,r],令当前答案为\(mid\)。
则若该操作是添加操作，如果其添加的\(C<=mid\)，这此次操作对于左子区间有贡献，加入左子区间中，并将区间线段树中的区间\([q[i].l,q[i].r]\)整体加\(1\).
反之，则将操作加入到右子区间中。
若该操作是询问操作，如果当前的\(mid\)在线段树中查询到的，比它大的数的个数\(query()>=q[i].k\)，则证明该询问操作应该在右子区间内可以找到答案。反之，则将\(q[i].k-=query()\)，减去此次查询的贡献，然后将询问操作添加到左子区间中。
#include#include #include #include using namespace std;#define int long longconst int N = 50000 + 5;struct Ask { int l, r, v, id, op; void read () { cin >> op >> l >> r >> v; } }q[N], tl[N], tr[N];int ans[N], tag[N << 2], clr[N << 2], sum[N << 2];int n, m, Q;#define lc (p << 1)#define rc (p << 1 | 1)#define mid ((l + r) >> 1)void pushdown (int p, int l, int r) { if (clr[p]) { clr[p] = 0; tag[lc] = tag[rc] = 0; sum[lc] = sum[rc] = 0; clr[lc] = 1, clr[rc] = 1; } if (tag[p]) { tag[lc] += tag[p]; tag[rc] += tag[p]; sum[lc] += tag[p] * (mid - l + 1); sum[rc] += tag[p] * (r - mid); tag[p] = 0; }} void push_up (int p) { sum[p] = sum[lc] + sum[rc];} void modify (int ql, int qr, int w, int p = 1, int l = 1, int r = n) { if (ql <= l && r <= qr){ tag[p] += w; sum[p] += w * (r - l + 1); return; } pushdown (p, l, r); if (ql <= mid) modify (ql, qr, w, lc, l, mid); if (mid < qr) modify (ql, qr, w, rc, mid + 1, r); push_up (p);}int query (int ql, int qr, int p = 1, int l = 1, int r = n) { if (ql <= l && r <= qr) { return sum[p]; } int ret = 0; pushdown(p,l,r); if (ql <= mid) ret += query (ql, qr, lc, l, mid); if (mid < qr) ret += query (ql, qr, rc, mid + 1, r); return ret;}void solve (int st, int en, int l, int r) { // [st, en] -> 处理操作的左右端点 // [l, r] -> 对应值域 if (l == r) { for (int i = st; i <= en; ++i) { if (q[i].op == 2) ans[q[i].id] = l; // 查询 } return; } int L = 0, R = 0; clr[1] = 1; tag[1] = sum[1] = 0; for (int i = st; i <= en; ++i) { if (q[i].op == 1){ if (q[i].v > mid) { // > mid 的操作对于答案 <= mid 的询问不会影响 modify (q[i].l, q[i].r, 1); tr[++R] = q[i]; } else { tl[++L] = q[i]; } } else { int val = query (q[i].l, q[i].r); if (val < q[i].v){ q[i].v -= val; tl[++L] = q[i]; // L部答案 <= mid }else{ tr[++R] = q[i]; // R部答案 > mid } } } for (int i = 1; i <= L; ++i) { q[st + i - 1] = tl[i]; } for (int i = L + 1; i <= L + R; ++i) { q[st + i - 1] = tr[i - L]; } solve (st, st + L - 1, l, mid); solve (st + L, en, mid + 1, r);}signed main () { cin >> n >> m; for (int i = 1; i <= m; ++i) { q[i].read (); if (q[i].op == 2) { q[i].id = ++Q; } } solve (1, m, -n, n); for (int i = 1; i <= Q; ++i) { cout << ans[i] << endl; }}