记录编号	557926	评测结果	AAAAAAAAAAAAAAA
题目名称	数列操作A	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.885 s
提交时间	2020-12-02 19:36:28	内存使用	7.81 MiB

#include <iostream>
#include <cstdio>
using namespace std;
const int maxN = 1e5 + 10;

struct Node{
	int l, r;
	int add;
	int sum;
}tree[maxN * 4];

int sum(int p, int l, int r);
void build(int p, int l, int r);
void add(int p, int l, int r, int d);

int n, m;
int origin[maxN];
int main(void){
	freopen("shulie.in", "r", stdin);
	freopen("shulie.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++)
		scanf("%d", origin + i);
	build(1, 1, n);
	scanf("%d", &m);
	for (int i = 1; i <= m; i ++){
		char opt[4];
		int x, y;
		scanf("%s", opt);
		if (opt[0] == 'S'){
			scanf("%d%d", &x, &y);
			printf("%d\n", sum(1, x, y));
		}
		else{
			scanf("%d%d", &x, &y);
			add(1, x, x, y); 
		}
	}
	return 0;
}

void build(int p, int l, int r){
	tree[p].l = l, tree[p].r = r;
	if (l == r){
		tree[p].sum = origin[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p <<1 | 1, mid + 1, r);
	tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
	return;
}

inline void pushdown(int p){
	if (tree[p].add){
		tree[p << 1].add = tree[p].add;
		tree[p << 1 | 1].add = tree[p].add;
		int mid = (tree[p].l + tree[p].r) >> 1;
		tree[p << 1].sum += tree[p].add * (mid - tree[p << 1].l + 1);
		tree[p << 1 | 1].sum += tree[p].add * (tree[p << 1 | 1].r - mid);
		tree[p].add = 0;
	}
	return;
}

void add(int p, int l, int r, int d){
	if (tree[p].l >= l && tree[p].r <= r){
		tree[p].sum += d * (tree[p].r - tree[p].l + 1);
		tree[p].add = d;
		return;
	}
	pushdown(p);
	if (tree[p << 1].r >= l)
		add(p << 1, l, r, d);
	if (tree[p << 1 | 1].l <= r)
		add(p << 1 | 1, l, r, d);
	tree[p].sum = tree[p << 1].sum + tree[p << 1 | 1].sum;
	return ;
}

int sum(int p, int l, int r){
	int anss = 0;
	if (tree[p].l >= l && tree[p].r <= r)
		return tree[p].sum;
	pushdown(p);
	if (tree[p << 1].r >= l)
		anss += sum(p << 1, l, r);
	if (tree[p << 1 | 1].l <= r)
		anss += sum(p << 1 | 1, l, r);
	return anss;
}