关于线段树
  • 板块学术版
  • 楼主封禁用户
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/10/25 08:22
  • 上次更新2024/10/25 11:23:23
查看原帖
关于线段树
608410
封禁用户楼主2024/10/25 08:22

请问这份板子有什么问题(顺便一问:把mid = (l + r) / 2写成mid = l + ((r - l) >> 1)会出问题吗

#include<bits/stdc++.h>

namespace IO {
	inline int read() {
		int ret = 0, f = 1;char ch = getchar();
		while (ch < '0' || ch > '9') {
			if (ch == '-') f = -f;
			ch = getchar();
		} 
		while (ch >= '0' && ch <= '9') {
			ret = (ret << 1) + (ret << 3) + (ch ^48);
			ch = getchar();
		}
		return ret * f;
	}
	void write(int x) {
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}

using namespace IO;
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

int a[maxn], sum[maxn * 4], L[maxn * 4], R[maxn * 4], lazy[maxn * 4];
int n, m;

int len(int x) {
	return R[x] - L[x] + 1;
}

void pushup(int x) {
	sum[x] = sum[x << 1] + sum[x << 1 | 1];
}

void pushdown(int x) {
	if (lazy[x]) {
		lazy[x << 1] += lazy[x];
		lazy[x << 1 | 1] += lazy[x];
		sum[x << 1] += lazy[x] * len(x << 1);
		sum[x << 1 | 1] += lazy[x] * len(x << 1 | 1);
		lazy[x] = 0;
	}
}

void build(int l, int r, int x) {
	L[x] = l, R[x] = r;
	if (l == r) {
		sum[x] = a[l];
		return;
	}
	int mid = l + ((r - l) >> 1);
	build(l, mid, x << 1);
	build(mid + 1, r, x << 1 | 1);
	pushup(x);
}

void update(int l, int r, int d, int x) {
	if (L[x] >= l && R[x] <= r) {
		lazy[x] += d;//  fuck you bro!!
		sum[x] += d * len(x);
		return;
	}
	pushdown(x);// !!!
	int mid = l + ((r - l) >> 1);
	if (l <= mid) update(l, r, d, x << 1);
	if (r > mid) update(l, r, d, x << 1 | 1);
	pushup(x);
}

ll query(int l, int r, int x) {
	if (L[x] >= l && R[x] <= r) {
		return sum[x];
	}
	pushdown(x);
	ll ans = 0LL;
	int mid = l + ((r - l) >> 1);
	if (l <= mid) ans += query(l, r, x << 1);
	if (r > mid) ans += query(l, r, x << 1 | 1);
//	pushup(x);
	return ans;
}

int main() {
	n = read(), m = read();
	for (int i = 1;i <= n;i++) a[i] = read();
	build(1, n, 1);
	while (m--) {
		int op = read(), x = read(), y = read(), k;
		if (op == 1) {
			k = read();
			update(x, y, k, 1);
		}
		else {
			ll ans = query(x, y, 1);
			printf("%lld", ans);
			//write(ans);
			puts("");
		}
	}
	return 0;
} 
2024/10/25 08:22
加载中...