为什么全部WA了啊
查看原帖
为什么全部WA了啊
213218
蒟蒻CGZ楼主2020/9/6 22:19

代码如下,样例的第三个回答错了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10;
ll n, m, a[N], add[4 * N], sum[4 * N];

inline ll read() {
	ll n = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if(c == '-') f = (~ f + 1);
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		n = (n << 3) + (n << 1) + (c ^ 48);
		c = getchar();
	}
	return n * f;
}

inline void build(ll k, ll l, ll r) { // 建树 
	if(l == r) {
		sum[k] = a[l];
		return;
	}
	ll mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	sum[k] = sum[k << 1] + sum[k << 1 | 1];
	return;
}

inline void Add(ll k, ll l, ll r, ll val) {
	add[k] += val;
	sum[k] += val * (r - l + 1);
}

inline void push_down(ll k, ll l, ll r, ll mid) { // 懒标记 
	if(!add[k]) return ;
	Add(k << 1, l, mid, add[k]);
	Add(k << 1 | 1, mid + 1, r, add[k]);
	add[k] = 0;
}

inline ll query(ll k, ll l, ll r, ll x, ll y) { // 区间查询 
	if(x <= l && r <= y)
		return sum[k];
	ll res = 0;
	ll mid = (l + r) >> 1;
	push_down(k, l, r, sum[k]);
	if(x <= mid) res += query(k << 1, l, mid, x, y);
	if(y > mid) res += query(k << 1 | 1, mid + 1, r, x, y);
	return res; 
}

inline void modify(ll k, ll l, ll r, ll x, ll y, ll val) { // 区间修改 
	if(x <= l && r <= y) {
		Add(k, l, r, val);
		return ;
	}
	ll mid = (l + r) >> 1;
	push_down(k, l, r, mid);
	if(x <= mid) modify(k << 1, l, mid, x, y, val);
	if(y > mid) modify(k << 1 | 1, mid + 1, r, x, y, val);
	sum[k] = sum[k << 1] + sum[k << 1 | 1];
	return ;
}

int main() {
	n = read();
	m = read();
	for (ll i = 1; i <= n; ++ i)
		a[i] = read();
	build(1, 1, n);
	ll opt, x, y, k;
	for (ll i = 1; i <= m; ++ i) {
		opt = read();
		if(opt == 1) {
			x = read(); y = read(); k = read();
			modify(1, 1, n, x, y, k);
		}
		else { // opt == 2
			x = read(); y = read();
			printf("%d\n", query(1, 1, n, x, y));
		}
	}
	return 0;
}
2020/9/6 22:19
加载中...