线段树模板求调
查看原帖
线段树模板求调
650705
cyx2117楼主2022/10/6 23:35

不知道有什么问题 蒟蒻真的看不出来了 求大佬帮忙看看

#include<iostream>
#include<cstdio>
#define ll long long 

using namespace std;

const int maxn = 1e5 + 10;
int n, m;
ll a[maxn], w[maxn * 4];
ll lzy[maxn * 4];

void pushup(const int u){
	w[u] = w[u * 2] + w[u * 2 + 1];
}

void build( int u, int L, int R){
	if(L == R){
		w[u] = a[L];
		return;
	}else{
		int mid = (L + R) >> 1;
		build(u * 2, L, mid);
		build(u * 2 + 1, mid + 1, R);
		pushup(u);
	}
}

bool InRange(int L, int R, int l, int r){
	return  (l <= L) && (r >= R);
}

bool OutofRange(int L, int R, int l, int r){
	return (R < l) || (L > r);
}

void maketag(int u, int len, int tag){
	lzy[u] += tag;
	w[u] += len * tag;
}

void pushdown(int u, int L, int R){
	int mid = (L + R) >> 1;
	maketag(u * 2, mid - L + 1, lzy[u]);
	maketag(u * 2 + 1, R - mid, lzy[u]);
	pushup(u);
	lzy[u] = 0;//下放标记后,原标记清零 
}

ll query(int u, int L, int R, int l, int r){
	if(InRange(L, R, l, r)){
		return w[u];
	}else if(!OutofRange(L, R, l, r)){
		int mid = (L + R) >> 1;
		pushdown(u, L, R);
		return query(u * 2, L, mid, l, r) + query(u * 2 + 1, mid + 1, R, l, r);
	}else return 0;
}

void update(int u, int L, int R, int l, int r, int x){
	if(InRange(L, R, l, r)){
		maketag(u, R - L + 1, x);
	}else if(!OutofRange(L, R, l, r)){
		int mid = (L + R) >> 1;
		pushdown(u, L, R);
		update(u * 2, L, mid, l, r, x);
		update(u * 2 + 1, mid + 1, R, l, r, x);
		pushup(u);
	}
}

int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		scanf("%lld", &a[i]);
	}
	for(int i = 0; i < m; i++){
		int op;
		scanf("%d", &op);
		if(op == 1){
			int x, y;
			ll k;
			scanf("%d%d%lld", &x, &y, &k);
			update(1, 1, n, x, y, k);
		}else if(op == 2){
			int x, y;
			scanf("%d%d", &x, &y);
			printf("%lld\n", query(1, 1, n, x, y));
		}  
	}
	return 0;
}
2022/10/6 23:35
加载中...