题目
题目描述
forever97家住迪拜一环，因此有很多大大小小的商场。
迪拜一环有n个超市，分别在坐标轴[1,n]位置，forever97家在0这个位置。
由于日常开销巨大，所以Trote_w经常让forever97出去买东西。
假如forever97现在要买k件物品，他会从第一家超市开始买东西，买完第一家之后向右走，直到买完k件物品为止。
在开始的时候，每个商店都是0个物品。
有以下两种操作：
1 l r x:代表[l,r]这个区间的超市都购入了x件物品
2 k:代表forever97要买入k个物品（注意：买完之后每个商店的商品会减少被购买的数量）
现在forever97想知道对于每个2操作，他走到哪个商店才能买完k个物品。
输入描述
多组数据
第一行一个T(1<=T<=10)代表样例组数
对于每组样例
第一行一个n(1<=n<=100000)代表商店个数，一个q(1<=q<=100000)代表操作次数。
接下来q行
每行为上述1操作或者2操作
\(1 \leq l \leq r \leq n\) \(1 \leq x \leq 10000\)
\(1 \leq k \leq 10^9\)
输出描述
对于每个2操作，输出一个数字y，代表forever97走到y商店能买完k件物品。
如果所有超市的物品总和不够k件，那么forever97会放弃这次购买，输出"Trote_w is sb"。
示例1
输入
1
5 6
2 1
1 1 5 5
2 12
2 12
2 12
2 1
输出
Trote_w is sb
3
5
Trote_w is sb
5
题解
知识点：线段树，二分。
这是一道典型的线段树上二分的题，询问采用二分选择递归区间，修改操作在区间加的基础上还需要清零标志。
具体地说，如果左区间的和大于等于 \(k\) ，则直接去左区间，否则将左区间清零去右区间。
实现时，清零的区间需要直接清零并设置懒标记，往下继续走的区间可以先不修改，因为最后回溯合并时会被一并修改。
时间复杂度 \(O((n+q) \log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct T {
int len;
ll sum;
static T e() { return { 0,0 }; }
friend T operator+(const T &a, const T &b) { return { a.len + b.len, a.sum + b.sum }; }
};
struct F {
bool cls;
ll add;
static F e() { return { 0,0 }; }
T operator()(const T &x) { return { x.len,cls ? x.len * add : x.sum + x.len * add }; }
F operator()(const F &g) { return { g.cls || cls,cls ? add : g.add + add }; }
};
struct SegmentTreeLazy {
int n;
vector<T> node;
vector<F> lazy;
void push_down(int rt) {
node[rt << 1] = lazy[rt](node[rt << 1]);
lazy[rt << 1] = lazy[rt](lazy[rt << 1]);
node[rt << 1 | 1] = lazy[rt](node[rt << 1 | 1]);
lazy[rt << 1 | 1] = lazy[rt](lazy[rt << 1 | 1]);
lazy[rt] = F::e();
}
void update(int rt, int l, int r, int x, int y, F f) {
if (r < x || y < l) return;
if (x <= l && r <= y) return node[rt] = f(node[rt]), lazy[rt] = f(lazy[rt]), void();
push_down(rt);
int mid = l + r >> 1;
update(rt << 1, l, mid, x, y, f);
update(rt << 1 | 1, mid + 1, r, x, y, f);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
}
int query(int rt, int l, int r, int val) {
if (l == r) return node[rt].sum -= val, l;
push_down(rt);
int mid = l + r >> 1;
int ans = 0;
if (node[rt << 1].sum >= val) ans = query(rt << 1, l, mid, val);
else {
int sum = node[rt << 1].sum;
node[rt << 1].sum = 0;
lazy[rt << 1] = { 1,0 };
ans = query(rt << 1 | 1, mid + 1, r, val - sum);
}
node[rt] = node[rt << 1] + node[rt << 1 | 1];
return ans;
}
public:
SegmentTreeLazy(int _n) { init(_n); }
void init(int _n) {
n = _n;
node.assign(n << 2, T::e());
lazy.assign(n << 2, F::e());
function<void(int, int, int)> build = [&](int rt, int l, int r) {
if (l == r) return node[rt] = { 1,0 }, void();
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
};
build(1, 1, n);
}
void update(int x, int y, F f) { update(1, 1, n, x, y, f); }
int query(int val) { return query(1, 1, n, val); }
};
bool solve() {
int n, q;
cin >> n >> q;
SegmentTreeLazy sgt(n);
while (q--) {
int op;
cin >> op;
if (op == 1) {
int l, r, x;
cin >> l >> r >> x;
sgt.update(l, r, { 0,x });
}
else {
int k;
cin >> k;
if (sgt.node[1].sum < k) cout << "Trote_w is sb" << '\n';
else cout << sgt.query(k) << '\n';
}
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}