模板题，折腾了许久。
cqd分治整体二分，感觉像是把询问分到答案上。
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drep(i, a, b) for (int i = a; i >= b; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second
using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
template <typename T> void Max(T &a, T &b) { if (a < b) a = b; }
template <typename T> void Min(T &a, T &b) { if (a > b) a = b; }
//****************************************** const int maxn = ; struct Seg_Tree {
int sum[maxn << ], lazy[maxn << ];
void Push_down(int o, int m) {
if (!lazy[o]) return;
lazy[o << ] += lazy[o], lazy[o << | ] += lazy[o];
sum[o << ] += lazy[o] * (m - (m >> )), sum[o << | ] += lazy[o] * (m >> );
lazy[o] = ;
}
void Push_up(int o) { sum[o] = sum[o << ] + sum[o << | ]; }
void update(int o, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) {
lazy[o] += v;
sum[o] += v * (r - l + );
return;
}
Push_down(o, r - l + );
int mid = l + r >> ;
if (ql <= mid) update(o << , l, mid, ql, qr, v);
if (qr > mid) update(o << | , mid + , r, ql, qr, v);
Push_up(o);
}
int query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return sum[o];
Push_down(o, r - l + );
int mid = l + r >> ;
int ret();
if (ql <= mid) ret += query(o << , l, mid, ql, qr);
if (qr > mid) ret += query(o << | , mid + , r, ql, qr);
return ret;
}
void CLR() { clr(sum), clr(lazy); }
} T; struct Complex {
int flag, x, y, c, id;
inline bool operator < (const Complex &A) const {
return id < A.id;
}
} src[maxn]; int N, ans[maxn], v[maxn];
void cdq(int ansl, int ansr, int l, int r) {
if (ansl == ansr) {
rep(i, l, r) if (src[i].flag == ) ans[src[i].id] = ansl;
return;
}
if (l > r) return;
sort(src + l, src + r + );
int m = ansl + ansr + >> ;
int j = l;
rep(i, l, r) {
if (src[i].flag == ) {
if (src[i].c >= m) T.update(, , N, src[i].x, src[i].y, ), v[i] = ;
else v[i] = ;
}
else {
int t = T.query(, , N, src[i].x, src[i].y);
if (t >= src[i].c) v[i] = ;
else src[i].c -= t, v[i] = ;
}
j += !v[i];
}
rep(i, l, r)
if (src[i].flag == )
if (src[i].c >= m) T.update(, , N, src[i].x, src[i].y, -);
int t = j - ;
if (j != l)
rep(i, l, t) {
while (j < r && v[j]) ++j;
if (v[i]) swap(src[i], src[j]), swap(v[i], v[j]), ++j;
}
cdq(ansl, m - , l, t);
cdq(m, ansr, t + , r);
} int read() {
int l = , s = ; char ch = getchar();
while (ch < '' || ch > '') { if (ch == '-') l = -; ch = getchar(); }
while (ch >= '' && ch <= '') { s = (s << ) + (s << ) + ch - ''; ch = getchar(); }
return s * l;
}
int main() {
int n, m; scanf("%d%d", &n, &m);
rep(i, , m) scanf("%d%d%d%d", &src[i].flag, &src[i].x, &src[i].y, &src[i].c), src[i].id = i;
N = n;
cdq(-n, n, , m);
sort(src + , src + + m);
rep(i, , m) if (src[i].flag == ) printf("%d\n", ans[i]);
return ;
}
树套树本来想把代表区间的那个线段树开在外面，不是不可以，但是lazy标记可能要一个vector才能存，因为我要存多个种类。
然后就只能把代表数字那一维开在外面，代表这一段数字在1-n这个区间的分布情况，这样就可以在第二层线段树上打lazy标记。
#include <bits/stdc++.h>
#define rep(i, a, b) for (register int i = a; i <= b; i++)
#define drep(i, a, b) for (register int i = a; i >= b; i--)
#define REP(i, a, b) for (register int i = a; i < b; i++)
#define pb push_back
#define mp make_pair
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second
using namespace std;
typedef long long i64;
typedef pair<int, int> pii;
const int inf = ~0U >> ;
const i64 INF = ~0ULL >> ;
//******************************* const int maxn = , maxnn = ; int root[maxn << ];
int ls[maxnn], rs[maxnn], sum[maxnn], lazy[maxnn]; int ndtot, n, N;
inline void Push_up(int o) { sum[o] = sum[ls[o]] + sum[rs[o]]; }
inline void Push_down(int o, int m) {
if (!lazy[o]) return;
if (!ls[o]) ls[o] = ++ndtot;
if (!rs[o]) rs[o] = ++ndtot;
lazy[ls[o]] += lazy[o], lazy[rs[o]] += lazy[o];
sum[ls[o]] += lazy[o] * (m - (m >> )), sum[rs[o]] += lazy[o] * (m >> );
lazy[o] = ;
}
void update(int &k, int l, int r, int ql, int qr, int v) {
if (!k) k = ++ndtot;
if (ql <= l && r <= qr) {
sum[k] += v * (r - l + );
lazy[k] += v;
return;
}
int mid = l + r >> ;
Push_down(k, r - l + );
if (ql <= mid) update(ls[k], l, mid, ql, qr, v);
if (qr > mid) update(rs[k], mid + , r, ql, qr, v);
Push_up(k);
}
void insrt(int o, int l, int r, int ql, int qr, int c) {
while (l != r) {
int mid = l + r >> ;
update(root[o], , n, ql, qr, );
if (c <= mid) o <<= , r = mid;
else o = o << | , l = mid + ;
}
update(root[o], , n, ql, qr, );
} int query(int o, int l, int r, int ql, int qr) {
if (!o) return ;
if (ql <= l && r <= qr) return sum[o];
Push_down(o, r - l + );
int mid = l + r >> ;
int ret();
if (ql <= mid) ret += query(ls[o], l, mid, ql, qr);
if (qr > mid) ret += query(rs[o], mid + , r, ql, qr);
return ret;
}
int solve(int o, int l, int r, int ql, int qr, int c) {
while (l != r) {
int mid = l + r >> ;
int t = query(root[o << | ], , n, ql, qr);
if (t >= c) l = mid + , o = o << |;
else r = mid, o = o << , c -= t;
}
return l;
} int main() {
int m; scanf("%d%d", &n, &m);
N = * n + ;
while (m--) {
int flag, a, b, c; scanf("%d%d%d%d", &flag, &a, &b, &c);
if (flag == ) {
c += n + ;
insrt(, , N, a, b, c);
}
else printf("%d\n", solve(, , N, a, b, c) - n - );
}
}