蓝桥杯算法提高VIP-分苹果 （C++代码）（线段树 lazy 练习）

解题思路:

        （ 反正没人看，注释不想写，写花了更难看，跑得挺慢的

参考代码:

#include<bits/stdc++.h>
using namespace std;

const int SIZE = 100002;
struct datas {
	int value, left, right, lazy;
} tree[SIZE << 2];

void buildtree(int root, int L, int R) {
	tree[root].left = L, tree[root].right = R;
	if (L == R)
		return;
	int mid = (L + R) >> 1;
	buildtree(root << 1, L, mid);
	buildtree(root << 1 | 1, mid + 1, R);
}

void pushdown(int root){
	tree[root << 1].lazy += tree[root].lazy;
	tree[root << 1 | 1].lazy += tree[root].lazy;
	tree[root << 1].value += (tree[root << 1].right - tree[root << 1].left + 1)
		* tree[root].lazy;
	tree[root << 1 | 1].value += (tree[root << 1 | 1].right - tree[root << 1 | 1].left + 1) 
		* tree[root].lazy;
	tree[root].lazy = 0;
}

void updata(int root, int L, int R, int Add) {
	if (tree[root].left == tree[root].right) {
		tree[root].value += Add; return;
	}
	if (tree[root].left == L && tree[root].right == R) {
		tree[root].value += (R - L + 1) * Add;
		tree[root].lazy += Add;
		return;
	}
	if(tree[root].lazy)
		pushdown(root);

	int mid = (tree[root].left + tree[root].right) >> 1;
	if (L > mid)
		updata(root << 1 | 1, L, R, Add);
	else if (R <= mid)
		updata(root << 1, L, R, Add);
	else {
		updata(root << 1 | 1, mid + 1, R, Add);
		updata(root << 1, L, mid, Add);
	}
}

void query(int root, int L, int R) {
	if (tree[root].lazy && tree[root].left != tree[root].right)
		pushdown(root);
	if (tree[root].left == tree[root].right) {
		printf("%d ", tree[root].value); return;
	}
	int mid = (tree[root].left + tree[root].value) >> 1;
	query(root << 1, L, mid);
	query(root << 1 | 1, mid + 1, R);
}

int main() {
	int total, que; scanf("%d%d", &total, &que);
	buildtree(1, 1, total);
	int L, R, Add;
	while (que--) {
		scanf("%d%d%d", &L, &R, &Add);
		updata(1, L, R, Add);
	}
	query(1, 1, total);
	printf("\n");
}