记录编号	577047	评测结果	AAAAAAAAAA
题目名称	[SYOI 2018] WHZ 的序列	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	2.123 s
提交时间	2022-10-22 09:17:59	内存使用	12.03 MiB

#include <bits/stdc++.h>
 
using i64 = long long;
 
const int N = 2e5 + 10;
int n, q;
i64 a[N];
 
int lowbit(int x) { return x & -x; }
 
struct T {
	i64 t1[N], t2[N];
	void add(int k, i64 v) {
		i64 v1 = k * v;
		for (; k <= n; k += lowbit(k)) 
			t1[k] += v, t2[k] += v1;
	}
	i64 getSum(i64 *t, int k) {
		i64 ret = 0;
		for (int x = k; x; x -= lowbit(x))
			ret += t[x];
		return ret;
	}
	void add1(int l, int r, int v) {
		add(r + 1, -v), add(l, v);
	}
	i64 getSum1(int l, int r) {
		return (r + 1LL) * getSum(t1, r) - 1LL * l * getSum(t1, l - 1) - 
			   (getSum(t2, r) - getSum(t2, l - 1));
	}
};
 
int L(int x, int flag) {
	if (x & 1) return (x + 1) / 2;
	else return x / 2 + flag;
}
 
int R(int x, int flag) {
	if (x & 1) return (x + 1) / 2 - (flag ^ 1);
	else return x / 2;
}
 
T t1, t2;
 
int main() {
	freopen("whz_sequence.in", "r", stdin); 
	freopen("whz_sequence.out", "w", stdout);
	std::cin >> n;
	for (i64 i = 1, x; i <= n; ++ i) {
		std::cin >> x;
		if (i & 1) t1.add1(L(i, 1), L(i, 1), x);
		else t2.add1(L(i, 0), L(i, 0), x);
	}
	std::cin >> q;
	while (q --) {
		i64 op, l, r, x;
		std::cin >> op;
		if (op == 1) {
			std::cin >> l >> r >> x;
			t1.add1(L(l, 1), R(r, 1), x),
			t2.add1(L(l, 0), R(r, 0), x);
		} else {
			std::cin >> l >> r;
			if (l & 1)
				std::cout << t1.getSum1(L(l, 1), R(r, 1)) - t2.getSum1(L(l, 0), R(r, 0)) << '\n';
			else
				std::cout << t2.getSum1(L(l, 0), R(r, 0)) - t1.getSum1(L(l, 1), R(r, 1)) << '\n';
		}
	}
	return 0;
}