一开始想的是区间线段树套权值线段树，结果好像不能实现。
然后题解是权值线段树套区间线段树。
区间线段树上标记永久化就省去了pushdown的操作减少常数。
标记永久化的话。。yy不出来就看代码吧。
然后注意开long long
#include#include #include #define N 50010#define LL long longusing namespace std;int n, m, t, cnt;LL sum[N * 200];int opt[N], a[N], b[N], c[N], g[N], add[N * 200], ls[N * 200], rs[N * 200], root[N << 2];inline int read(){ int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0'; return x * f;}inline void insert2(int &now, int l, int r, int x, int y){ if(!now) now = ++cnt; if(x <= l && r <= y) { add[now]++; sum[now] += r - l + 1; return; } int mid = (l + r) >> 1; if(x <= mid) insert2(ls[now], l, mid, x, y); if(mid < y) insert2(rs[now], mid + 1, r, x, y); sum[now] = sum[ls[now]] + sum[rs[now]] + (LL)(r - l + 1) * add[now];}inline void insert1(int now, int l, int r, int d, int x, int y){ insert2(root[now], 1, n, x, y); if(l == r) return; int mid = (l + r) >> 1; if(d <= mid) insert1(now << 1, l, mid, d, x, y); else insert1(now << 1 | 1, mid + 1, r, d, x, y);}inline LL query2(int now, int l, int r, int x, int y){ if(x <= l && r <= y) return sum[now]; LL tmp = 0; int mid = (l + r) >> 1; if(x <= mid) tmp += query2(ls[now], l, mid, x, y); if(mid < y) tmp += query2(rs[now], mid + 1, r, x, y); return tmp + (LL)(min(r, y) - max(l, x) + 1) * add[now];}inline int query1(int now, int l, int r, LL d, int x, int y){ if(l == r) return l; int mid = (l + r) >> 1; LL tmp = query2(root[now << 1 | 1], 1, n, x, y); if(tmp < d) return query1(now << 1, l, mid, d - tmp, x, y); else return query1(now << 1 | 1, mid + 1, r, d, x, y);}int main(){ int i; n = read(); m = read(); for(i = 1; i <= m; i++) { opt[i] = read(); a[i] = read(), b[i] = read(), c[i] = read(); if(opt[i] == 1) g[++t] = c[i]; } sort(g + 1, g + t + 1); t = unique(g + 1, g + t + 1) - g - 1; for(i = 1; i <= m; i++) if(opt[i] == 1) { c[i] = lower_bound(g + 1, g + t + 1, c[i]) - g; insert1(1, 1, t, c[i], a[i], b[i]); } else printf("%d\n", g[query1(1, 1, t, c[i], a[i], b[i])]); return 0;}