题目大意：有$n$个位置，$m$个操作。操作有两种：
- $1\;l\;r\;x：$在区间$[l,r]$每个位置加上一个数$x$
- $2\;l\;r\;k：$询问$[l,r]$中第$k$大的数是多少。
题解：树套树，权值线段树套位置线段树，要标记永久化，不然会$TLE$
卡点：没有标记永久化，$TLE$，然后处理$tag$部分写错
C++ Code：
#include <cstdio>
#include <algorithm>
#include <cctype>
namespace __IO {
namespace R {
int x, ch, f;
inline int readsign() {
f = 1;
while (isspace(ch = getchar()));
if (ch == '-') f = -1;
for (x = ch & 15; isdigit(ch = getchar()); ) x = x * 10 + (ch & 15);
return x * f;
}
inline int read() {
while (isspace(ch = getchar()));
for (x = ch & 15; isdigit(ch = getchar()); ) x = x * 10 + (ch & 15);
return x;
}long long X;
inline long long readll() {
while (isspace(ch = getchar()));
for (X = ch & 15; isdigit(ch = getchar()); ) X = X * 10 + (ch & 15);
return X;
}
}
}
using __IO::R::read;
using __IO::R::readsign;
using __IO::R::readll;#define maxn 50010int n, m;namespace SgT2 {
#define N ((maxn << 3) * 50)
int lc[N], rc[N], tg[N], idx;
int L, R;
long long V[N];void __insert(int &rt, const int l, const int r) {
if (!rt) rt = ++idx;
V[rt] += std::min(R, r) - std::max(L, l) + 1;
if (L <= l && R >= r) {
tg[rt]++;
return ;
}
int mid = l + r >> 1;
if (L <= mid) __insert(lc[rt], l, mid);
if (R > mid) __insert(rc[rt], mid + 1, r);
}
void insert(int &rt, int __L, int __R) {
L = __L, R = __R;
__insert(rt, 1, n);
}long long __query(const int rt, const int l, const int r) {
if (!rt || (L <= l && R >= r)) return V[rt];
int mid = l + r >> 1;
long long res = static_cast<long long> (std::min(R, r) - std::max(L, l) + 1) * tg[rt];
if (L <= mid) res += __query(lc[rt], l, mid);
if (R > mid) res += __query(rc[rt], mid + 1, r);
return res;
}
long long query(int rt, int __L, int __R) {
L = __L, R = __R;
return __query(rt, 1, n);
}
#undef N
}namespace SgT {
#define N (maxn << 3)
const int maxl = -50000, maxr = 50000;
int root[N];
int L, R, num;
void __insert(const int rt, const int l, const int r) {
SgT2::insert(root[rt], L, R);
if (l == r) return ;
int mid = l + r >> 1;
if (num <= mid) __insert(rt << 1, l, mid);
else __insert(rt << 1 | 1, mid + 1, r);
}
void insert(int __L, int __R, int __num) {
L = __L, R = __R, num = __num;
__insert(1, maxl, maxr);
}long long pos;
int __query(const int rt, const int l, const int r) {
if (l == r) return l;
int mid = l + r >> 1;
long long tmp = SgT2::query(root[rt << 1 | 1], L, R);
if (pos <= tmp) return __query(rt << 1 | 1, mid + 1, r);
else {
pos -= tmp;
return __query(rt << 1, l, mid);
}
}
int query(int __L, int __R, long long __pos) {
L = __L, R = __R, pos = __pos;
return __query(1, maxl, maxr);
}
#undef N
}
using SgT::insert;
using SgT::query;int main() {
n = read(), m = read();
while (m --> 0) {
int op = read(), l = read(), r = read();
if (op == 1) {
int c = readsign();
insert(l, r, c);
} else {
long long c = readll();
printf("%d\n", query(l, r, c));
}
}
return 0;
}
