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

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 200010;
int n, m, s, a[MAXN], sum[2][MAXN], tag[MAXN];
void update(int x, int y, int w) {
	int ka = x / s, kb = y / s;
	if(ka == kb) {
		for(int i = x; i <= y; i ++) {
			a[i] += w;
			sum[i % 2][ka] += w;
		}
		return ;
	}
	for(int i = x; i < (ka + 1) * s; i ++) {
		a[i] += w;
		sum[i % 2][ka] += w;
	}
	for(int i = kb * s; i <= y; i ++) {
		a[i] += w;
		sum[i % 2][kb] += w;
	}
	for(int i = ka + 1; i < kb; i ++) {
		tag[i] += w;
		sum[0][i] += w * (s / 2);
		sum[1][i] += w * (s / 2);
		if(s % 2 != 0) {
			int u = i * s;
			sum[u % 2][i] += w;
		}
	}
}
void query(int x, int y) {
	int ka = x / s, kb = y / s, ans = 0;
	if(ka == kb) {
		for(int i = x; i <= y; i ++) {
			if((i - 1) % 2 == 0) {
				ans += a[i] + tag[ka];
			}
			else {
				ans -= a[i] + tag[ka];
			}
		}
		if((x - 1) % 2 == 1) {
			ans = -ans;
		}
		cout << ans << endl;
		return ;
	}
	for(int i = x; i < (ka + 1) * s; i ++) {
		if((i - 1) % 2 == 0) {
			ans += a[i] + tag[ka];
		}
		else {
			ans -= a[i] + tag[ka];
		}
	}
	for(int i = kb * s; i <= y; i ++) {
		if((i - 1) % 2 == 0) {
			ans += a[i] + tag[kb];
		}
		else {
			ans -= a[i] + tag[kb];
		}
	}
	for(int i = ka + 1; i < kb; i ++) {
		ans += sum[1][i];
		ans -= sum[0][i];
	}
	if((x - 1) % 2 == 1) {
		ans = -ans;
	}
	cout << ans << endl;
}
signed main() {
    freopen("whz_sequence.in", "r", stdin);
    freopen("whz_sequence.out", "w", stdout);
	cin >> n;
	s = sqrt(n);
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
		sum[i % 2][i / s] += a[i];
	}
	cin >> m;
	for(int i = 1; i <= m; i ++) {
		int op, x, y, w;
		cin >> op >> x >> y;
		if(op == 1) {
			cin >> w;
			update(x, y, w);
		}
		else {
			query(x, y);
		}
	}
	return 0;
}

//本来打的分块，打不出来，又打了莫队，错了，又打了分块，终于对了QAQ 
//寄了注释没删QAQ