174 lines
4.9 KiB
C++
174 lines
4.9 KiB
C++
#include <algorithm>
|
||
#include <iostream>
|
||
#include <cstring>
|
||
|
||
using namespace std;
|
||
typedef long long LL;
|
||
|
||
//快读
|
||
LL read() {
|
||
LL x = 0, f = 1;
|
||
char ch = getchar();
|
||
while (ch < '0' || ch > '9') {
|
||
if (ch == '-') f = -1;
|
||
ch = getchar();
|
||
}
|
||
while (ch >= '0' && ch <= '9') {
|
||
x = (x << 3) + (x << 1) + (ch ^ 48);
|
||
ch = getchar();
|
||
}
|
||
return x * f;
|
||
}
|
||
const int N = 200010;
|
||
|
||
LL ans[N]; //每个询问的答案
|
||
int n, m; //原始n个数字，共m个操作
|
||
|
||
//线段树结构体
|
||
#define ls u << 1
|
||
#define rs u << 1 | 1
|
||
struct Node {
|
||
int l, r; //区间范围
|
||
LL lazy; //区间修改懒标记
|
||
LL sum; //区间和
|
||
} tr[N << 2];
|
||
|
||
//向上更新统计信息:区间和
|
||
void pushup(int u) {
|
||
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
||
}
|
||
|
||
//向下传递区间修改标记
|
||
void pushdown(int u) {
|
||
//如果懒标记为0,没有可以传递
|
||
if (!tr[u].lazy) return;
|
||
|
||
//向下传递lazy标志
|
||
tr[ls].lazy += tr[u].lazy, tr[rs].lazy += tr[u].lazy; //加法有叠加性
|
||
|
||
//用lazy通过计算，更新左右儿子的sum值
|
||
int l = tr[u].l, r = tr[u].r;
|
||
int mid = (l + r) >> 1;
|
||
tr[ls].sum += tr[u].lazy * (mid - l + 1);
|
||
tr[rs].sum += tr[u].lazy * (r - mid);
|
||
|
||
// lazy标记清零
|
||
tr[u].lazy = 0;
|
||
}
|
||
|
||
//构建线段树
|
||
void build(int u, int l, int r) {
|
||
tr[u] = {l, r, 0, 0};
|
||
if (l == r) return;
|
||
int mid = (l + r) >> 1;
|
||
build(ls, l, mid), build(rs, mid + 1, r);
|
||
}
|
||
|
||
//区间更新
|
||
//之所以参数起名为[ql,qr]因为这是查询区间，而不是构建区间
|
||
void modify(int u, int ql, int qr, LL c) {
|
||
int l = tr[u].l, r = tr[u].r; //将变量名l,r保留下来给tr[u].l,tr[u].r
|
||
if (ql <= l && qr >= r) { // u结点的管辖范围[tr[u].l~tr[u].r]完整命中
|
||
tr[u].lazy += c; //区间修改加上lazy标记,这样就不用现在就逐层下传了
|
||
tr[u].sum += c * (r - l + 1); //对统计信息进行更新,完成本层的统计信息更新
|
||
return;
|
||
}
|
||
|
||
//下面要进行分裂，分裂前需要pushdown
|
||
pushdown(u);
|
||
|
||
int mid = (l + r) >> 1;
|
||
if (ql <= mid) modify(ls, ql, qr, c); //与左儿子区间有交集，递归左儿子
|
||
if (mid < qr) modify(rs, ql, qr, c); //与右儿子区间有交集，递归右儿子
|
||
|
||
//向上更新统计信息
|
||
pushup(u);
|
||
}
|
||
|
||
//查询区间sum和
|
||
LL query(int u, int ql, int qr) {
|
||
int l = tr[u].l, r = tr[u].r;
|
||
if (ql <= l && r <= qr) return tr[u].sum; //完整命中，返回区间和
|
||
|
||
LL res = 0;
|
||
//分裂前需要pushdown
|
||
pushdown(u);
|
||
int mid = (l + r) >> 1;
|
||
if (ql <= mid) res += query(ls, ql, qr); //与左儿子区间有交集，递归左儿子
|
||
if (mid < qr) res += query(rs, ql, qr); //与右儿子区间有交集，递归右儿子
|
||
return res;
|
||
}
|
||
|
||
//整体二分的查询结构体
|
||
struct Q {
|
||
int op, l, r;
|
||
LL k;
|
||
int id;
|
||
} q[N], q1[N], q2[N];
|
||
|
||
//整体二分
|
||
void solve(int l, int r, int ql, int qr) {
|
||
if (ql > qr) return; //无效查询区间，防RE
|
||
|
||
if (l == r) {
|
||
for (int i = ql; i <= qr; i++)
|
||
if (q[i].op == 2) ans[q[i].id] = l; //二分标识答案
|
||
return;
|
||
}
|
||
|
||
int mid = (l + r) >> 1;
|
||
int nl = 0, nr = 0;
|
||
for (int i = ql; i <= qr; i++) {
|
||
if (q[i].op == 1) { //增加
|
||
if (q[i].k > mid) {
|
||
modify(1, q[i].l, q[i].r, 1); //用线段树指定区全都+1
|
||
q1[++nl] = q[i]; //加入左增加操作
|
||
} else
|
||
q2[++nr] = q[i]; //加入右增加操作
|
||
} else { //查询
|
||
LL t = query(1, q[i].l, q[i].r);
|
||
if (t >= q[i].k)
|
||
q1[++nl] = q[i];
|
||
else {
|
||
q[i].k -= t;
|
||
q2[++nr] = q[i];
|
||
}
|
||
}
|
||
}
|
||
//有加就有减
|
||
for (int i = ql; i <= qr; i++)
|
||
if (q[i].op == 1)
|
||
if (q[i].k > mid) modify(1, q[i].l, q[i].r, -1);
|
||
|
||
//合并到q数组
|
||
for (int i = ql; i < ql + nl; i++) q[i] = q1[i - ql + 1];
|
||
for (int i = ql + nl; i <= qr; i++) q[i] = q2[i - ql - nl + 1];
|
||
|
||
//递归左右
|
||
solve(mid + 1, r, ql, ql + nl - 1), solve(l, mid, ql + nl, qr);
|
||
}
|
||
int main() {
|
||
//原序列n个数字，共m个操作
|
||
n = read(), m = read();
|
||
|
||
//构建线段树
|
||
build(1, 1, n);
|
||
|
||
int qc = 0; //查询的个数
|
||
for (int i = 1; i <= m; i++) {
|
||
int op = read(), l = read(), r = read(), k = read();
|
||
if (op == 2) //查询操作
|
||
q[i] = {op, l, r, k, ++qc};
|
||
else // 增加操作 op=1
|
||
// 1 l r k : op=1 增加，[l,r]:增加k
|
||
q[i] = {op, l, r, k};
|
||
}
|
||
|
||
//整体二分
|
||
solve(-1e9, 1e9, 1, m);
|
||
|
||
//输出
|
||
for (int i = 1; i <= qc; i++) printf("%lld\n", ans[i]);
|
||
|
||
return 0;
|
||
} |