本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-23 11:28:54

考虑到题目中的操作实际上就是给区间加上某个值，询问就是问某点和第一次大于等于 $k$ 的时间。

考虑到可以直接用可持久化线段树模拟这个过程。

可持久化线段树是可以用标记永久化的方法来实现某些区间操作的。具体来说，我们不将某个点上的标记下传，而是在询问时一路加上所有标记。

然后二分一个最早的树即可。实现不难。

#include <iostream>
using namespace std;
using i64 = long long;
const int N = 1e6 + 10;
struct node { i64 s; int l, r; } sg[20 * N];
int rt[N], id[N], cnt = 0;

void upd (int &u, int v, int x, int y, int l, int r, i64 k)
{
	int mid = (x + y) \/ 2;
	sg[u = ++cnt] = sg[v];
	if (l <= x && y <= r) return sg[u].s += k, void ();
	if (l <= mid) upd (sg[u].l, sg[v].l, x, mid, l, r, k);
	if (r > mid) upd (sg[u].r, sg[v].r, mid + 1, y, l, r, k);
}

i64 qry (int u, int x, int y, int p, i64 tag)
{
	int mid = (x + y) \/ 2;
	if (x == y) return sg[u].s + tag;
	if (p <= mid) return qry (sg[u].l, x, mid, p, tag + sg[u].s);
	else return qry (sg[u].r, mid + 1, y, p, tag + sg[u].s);
}

int main (void)
{
	int n, q, qid = 0;
	
	cin.tie (0)->sync_with_stdio (false);
	cin >> n >> q;
	for (int i = 1; i <= q; i++) {
		int opt;
		
		cin >> opt;
		if (opt == 1) {
			int x;
			i64 y, k;
			cin >> x >> y >> k;
			id[++qid] = i, upd (rt[qid], rt[qid - 1], 1, n, x, y, k);
		}
		else {
			int l = 1, r = qid, ans = -1, x;
			i64 y;
			
			cin >> x >> y;
			
			if (qry (rt[qid], 1, n, x, 0) < y) {
				cout << "0\n";
				continue;
			}
			
			while (l <= r) {
				int mid = (l + r) \/ 2;
				if (qry (rt[mid], 1, n, x, 0) >= y) r = (ans = mid) - 1;
				else l = mid + 1;
			}
			
			cout << id[ans] << '\n';
		}
	}
	return 0;