你妈的，权值可以是负数，所以 lazytag 的初值不能是 $0$，调了一个下午。

换句话说，你 pushdown 不应该这样写：

void pushdown(int l, int r, int pos) {
	if (!tag[pos]) return;
	int mid = (l + r) >> 1;
	lazy(l, mid, ls, tag[pos]), lazy(mid + 1, r, rs, tag[pos]);
	tag[pos] = 0;
}

而是应该赋值 tag[i]=inf，然后判 if (tag[pos] == inf) return。

下面是 datamaker，供大家对拍用。建树部分的时间非常 low，不过拍上 $n=100$ 也差不多了。

#include <bits/stdc++.h>
inline int rnd(int l, int r) {static int seed = rand(); seed = (((seed * 666666ll + 20050818) % 998244353) ^ 1000000007) % 1004535809; return seed % (r - l + 1) + l;}
int fa[100005];
int get(int x) {
	if (x == fa[x]) {
		return x;
	} else {
		return fa[x] = get(fa[x]);
	}
}
void merge(int u, int v) {
	u = get(u), v = get(v);
	fa[u] = v;
}
int main() {
	srand(time(nullptr));
	int n = 1000, q = 1100000;
	printf("%d\n", n);
	for (int i = 1; i <= n; i++) {
		printf("%d ", rnd(-5, 10));
	}
	puts("");
	
	for (int i = 1; i <= n; i++) {
		fa[i] = i;
	}
	for (int i = 1; i < n; i++) {
		while (true) {
			int u = rnd(1, n), v = rnd(1, n);
			if (get(u) != get(v)) {
				printf("%d %d\n", u, v);
				merge(u, v);
				break;
			}
		}
	}
	
	printf("%d\n", q);
	while (q--) {
		int op = rnd(2, 2);
		if (op == 1) {
			printf("%d %d %d\n", op, rnd(1, n), rnd(1, n));
		} else {
			printf("%d %d %d %d\n", op, rnd(1, n), rnd(1, n), rnd(-5, 10));
		}
	}
	return 0;
}