「ZJOI2013」K大数查询
整体二分，修改的时候用线段树代替树状数组即可。
参考代码：
#include <cstdio>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
template < class T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while ('0' > c || c > '9') f |= c == '-', c = getchar();
while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
s = f ? -s : s;
}typedef long long LL;
const int _ = 5e4 + 5;int n, m, q, res[_]; LL sum[_ << 2]; int tag[_ << 2];
struct node { int opt, l, r; LL c; int id; } t[_], tt1[_], tt2[_];inline int lc(int p) { return p << 1; }inline int rc(int p) { return p << 1 | 1; }inline void pushup(int p) { sum[p] = sum[lc(p)] + sum[rc(p)]; }inline void f(int p, int l, int r, int v) { sum[p] += 1ll * v * (r - l + 1), tag[p] += v; }inline void pushdown(int p, int l, int r, int mid)
{ if (tag[p]) f(lc(p), l, mid, tag[p]), f(rc(p), mid + 1, r, tag[p]), tag[p] = 0; }inline void update(int ql, int qr, int v, int p = 1, int l = 1, int r = n) {
if (ql <= l && r <= qr) return f(p, l, r, v);
int mid = (l + r) >> 1;
pushdown(p, l, r, mid);
if (ql <= mid) update(ql, qr, v, lc(p), l, mid);
if (qr > mid) update(ql, qr, v, rc(p), mid + 1, r);
pushup(p);
}inline LL query(int ql, int qr, int p = 1, int l = 1, int r = n) {
if (ql <= l && r <= qr) return sum[p];
int mid = (l + r) >> 1; LL res = 0;
pushdown(p, l, r, mid);
if (ql <= mid) res += query(ql, qr, lc(p), l, mid);
if (qr > mid) res += query(ql, qr, rc(p), mid + 1, r);
return res;
}inline void solve(int ql, int qr, int l, int r) {
if (ql > qr || l > r) return ;
if (l == r) { for (rg int i = ql; i <= qr; ++i) if (t[i].opt == 2) res[t[i].id] = l; return ; }
int mid = (l + r) >> 1, p1 = 0, p2 = 0;
for (rg int i = ql; i <= qr; ++i) {
if (t[i].opt == 1) {
if (t[i].c <= mid) tt1[++p1] = t[i]; else update(t[i].l, t[i].r, 1), tt2[++p2] = t[i];
} else {
LL cnt = query(t[i].l, t[i].r);
if (cnt < t[i].c) t[i].c -= cnt, tt1[++p1] = t[i]; else tt2[++p2] = t[i];
}
}
for (rg int i = 1; i <= p2; ++i) if (tt2[i].opt == 1) update(tt2[i].l, tt2[i].r, -1);
for (rg int i = 1; i <= p1; ++i) t[ql + i - 1] = tt1[i];
for (rg int i = 1; i <= p2; ++i) t[ql + p1 + i - 1] = tt2[i];
solve(ql, ql + p1 - 1, l, mid), solve(ql + p1, qr, mid + 1, r);
}int main() {
read(n), read(m);
for (rg int i = 1; i <= m; ++i)
read(t[i].opt), read(t[i].l), read(t[i].r), read(t[i].c), t[i].id = t[i].opt == 2 ? ++q : 0;
solve(1, m, 0, n);
for (rg int i = 1; i <= q; ++i) printf("%d\n", res[i]);
return 0;
}
