题目描述
由乃不太会打扑克
所以她出了一个数据结构题
给你一个长为 n 的序列 a，需要支持 m 次操作，操作有两种：
- 查询区间 [l,r] 的第 k 小值。
- 区间 [l,r] 加上 k。
输入格式
一行两个整数 n,m。
接下来一行 n 个整数， 第 i 个整数表示 a_i。
接下来 m 行，每行四个数 opt,l,r,k，其中 opt 代表是哪种操作。
输出格式
对于每个询问输出一个数表示答案，如果无解输出 -1。
输入输出样例 #1
输入 #1
1 1
1
1 1 1 1
输出 #1
1
说明/提示
1\leq n,m\leq 10^5，-2\times 10^4\leq 每次加上的数和原序列的数 \leq 2\times 10^4。
\text{upd 2022.8.18}：新增加一组 Hack 数据。
TLE：
#include <iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5, inf = 2e9;
int n, q, num, s;
int a[maxn], t[maxn], belong[maxn], st[maxn], en[maxn], delta[maxn], minv[maxn], maxv[maxn];
inline int read() {
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
void SORT(int x) {
int l = st[x], r = en[x];
for (int i = l; i <= r; ++i) t[i] = a[i];
sort(t + l, t + r + 1);
minv[x] = t[l];
maxv[x] = t[r];
}
int count_less(int w, int l, int r) {
int x = belong[l], y = belong[r], res = 0;
if (x == y) {
for (int i = l; i <= r; ++i)
if (a[i] + delta[x] < w) res++;
return res;
}
for (int i = l; i <= en[x]; ++i)
if (a[i] + delta[x] < w) res++;
for (int i = st[y]; i <= r; ++i)
if (a[i] + delta[y] < w) res++;
for (int i = x + 1; i < y; ++i) {
int target = w - delta[i];
int cnt = lower_bound(t + st[i], t + en[i] + 1, target) - (t + st[i]);
res += cnt;
}
return res;
}
int main() {
n = read(); q = read();
s = 500;
num = (n + s - 1) / s;
for (int i = 1; i <= num; ++i) {
st[i] = (i - 1) * s + 1;
en[i] = min(i * s, n);
for (int j = st[i]; j <= en[i]; ++j) belong[j] = i;
}
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= num; ++i) SORT(i);
while (q--) {
int op = read(), l = read(), r = read(), k = read();
if (op == 2) {
int x = belong[l], y = belong[r];
if (x == y) {
for (int i = st[x]; i <= en[x]; ++i) a[i] += delta[x];
delta[x] = 0;
for (int i = l; i <= r; ++i) a[i] += k;
SORT(x);
} else {
for (int i = st[x]; i <= en[x]; ++i) a[i] += delta[x];
delta[x] = 0;
for (int i = l; i <= en[x]; ++i) a[i] += k;
SORT(x);
for (int i = st[y]; i <= en[y]; ++i) a[i] += delta[y];
delta[y] = 0;
for (int i = st[y]; i <= r; ++i) a[i] += k;
SORT(y);
for (int i = x + 1; i < y; ++i) delta[i] += k;
}
} else {
if (k > r - l + 1) {
write(-1); putchar('\n');
continue;
}
int L = inf, R = -inf;
for (int i = 1; i <= num; ++i) {
if (en[i] < l || st[i] > r) continue;
int curr_min = minv[i] + delta[i];
int curr_max = maxv[i] + delta[i];
if (curr_min < L) L = curr_min;
if (curr_max > R) R = curr_max;
}
int ans = L - 1;
while (L <= R) {
int mid = (0LL + L + R) >> 1;
int cnt = count_less(mid, l, r);
if (cnt < k) {
ans = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
write(ans); putchar('\n');
}
}
return 0;
}
