比赛 数据结构模板题 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 数列操作C 最终得分 100
用户昵称 LikableP 运行时间 1.393 s
代码语言 C++ 内存使用 7.67 MiB
提交时间 2025-04-15 19:01:15
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <fstream>
#define ls(root) root << 1
#define rs(root) root << 1 | 1
#define Merge(root) tree[root] = tree[ls(root)] + tree[rs(root)]
using namespace std;
typedef long long ll;

const int MAXN = 1e5;

int n, m;
ll a[MAXN + 10];

ll tree[(MAXN << 2) + 10], lazy[(MAXN << 2) + 10];
void PushDown(int root, int lt, int rt) {
	if (lazy[root]) {
		int mid = lt + ((rt - lt) >> 1);
		tree[ls(root)] += (mid - lt + 1) * 1ll * lazy[root];
		lazy[ls(root)] += lazy[root];
		tree[rs(root)] += (rt - mid) * 1ll * lazy[root];
		lazy[rs(root)] += lazy[root];
		lazy[root] = 0;
	}
	return ;
}

void Build(int root, int lt, int rt) {
	if (lt == rt) {
		tree[root] = a[rt];
		return ;
	} 
	int mid = lt + ((rt - lt) >> 1);
	Build(ls(root), lt, mid);
	Build(rs(root), mid + 1, rt);
	Merge(root);
	return ;
}

void AddSeq(int root, int lt, int rt, int lq, int rq, int val) {
	if (lt == lq && rt == rq) {
		tree[root] += (rt - lt + 1) * 1ll * val;
		lazy[root] += val;
		return ;
	} 
	PushDown(root, lt, rt);
	int mid = lt + ((rt - lt) >> 1);
	if (rq <= mid) {
		AddSeq(ls(root), lt, mid, lq, rq, val);
	} else if (lq > mid) {
		AddSeq(rs(root), mid + 1, rt, lq, rq, val);
	} else {
		AddSeq(ls(root), lt, mid, lq, mid, val);
		AddSeq(rs(root), mid + 1, rt, mid + 1, rq, val);
	}
	Merge(root);
	return ;
}

ll GetSeq(int root, int lt, int rt, int lq, int rq) {
	if (lt == lq && rt == rq) {
		return tree[root];
	}
	PushDown(root, lt, rt);
	int mid = lt + ((rt - lt) >> 1);
	if (rq <= mid) {
		return GetSeq(ls(root), lt, mid, lq, rq);
	} else if (lq > mid) {
		return GetSeq(rs(root), mid + 1, rt, lq, rq);
	} else {
		return GetSeq(ls(root), lt, mid, lq, mid) + GetSeq(rs(root), mid + 1, rt, mid + 1, rq);
	}
}

int main() {
	freopen("shuliec.in", "r", stdin);
	freopen("shuliec.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	Build(1, 1, n);
	scanf("%d", &m);
	while (m--) {
		char op[10];
		scanf("%s", op);
		if (op[0] == 'A') {
			int i, j, d;
			scanf("%d %d %d", &i, &j, &d);
			AddSeq(1, 1, n, i, j, d);
		} else if (op[0] == 'S') {
			int s, t;
			scanf("%d %d", &s, &t);
			printf("%lld\n", GetSeq(1, 1, n, s, t));
		} else {
			printf("QwQ");
		}
	}
	return 0;
}