UT_MC_wuming @ 2023-08-09 19:11:37
#include <bits/stdc++.h>
using namespace std;
#define _M (st+en)/2
int arr[114514 * 4], tree[114514 * 4], n, m, k, op, x, y;//树状数组要*4!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
void Build_tree(int root, int st, int en) {
if (st == en) {
tree[root] = arr[st];
return;
}
int mid = _M;
//cout << mid << endl;
int l_root = 2 * root;
int r_root = 2 * root + 1;
Build_tree(l_root, st, mid);
Build_tree(r_root, mid + 1, en);
tree[root] = tree[l_root] + tree[r_root];
}
void Opt_add(int root, int st, int en, int l, int r, int num) {
/*if (st>r || en<l)return;//剪枝,[st,en]不在[l,r]内时跳出
if (st == en) {
tree[root] += num;
return;
}
int mid = _M;
int l_root = 2 * root;
int r_root = 2 * root + 1;
Opt_add(l_root,st,mid,l,r,num);
Opt_add(r_root,mid+1,en,l,r,num);
tree[root] = tree[l_root] + tree[r_root];
*/
//以上为小杯做法
int lazy[114514*4];
if (st > r || en < l)return;
if (l <= st && en <= r) {
tree[root] += (en - st + 1) * num;
lazy[root] += num;
return;
}
int mid = _M;
if (st != en && lazy[root]) {
tree[root * 2] += lazy[root] * (mid - st + 1);
tree[root * 2 + 1] += lazy[root] * (en - mid);
lazy[root * 2] += lazy[root];
lazy[root * 2 + 1] += lazy[root];
lazy[root] = 0;
}
if (l <= mid) Opt_add(root * 2, st, mid, l, r, num);
if (r > mid) Opt_add(root * 2 + 1, mid + 1, en, l, r, num);
tree[root] = tree[root * 2] + tree[root * 2 + 1];
}
int Opt_query(int root, int st, int en, int l, int r) {
if (st > r || en < l)return 0;//剪枝,[st,en]不在[l,r]内时跳出
if (st == en || (l <= st && en <= r)) {
return tree[root];
}
int mid = _M;
int l_root = 2 * root;
int r_root = 2 * root + 1;
int sum1 = Opt_query(l_root, st, mid, l, r);
int sum2 = Opt_query(r_root, mid + 1, en, l, r);
return sum1 + sum2;
//你说的对但是我return l_root+r_root是**
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}Build_tree(1, 1, n);
for (int i = 1; i <= m; i++) {
cin >> op;
if (op == 1) {
cin >> x >> y >> k;
Opt_add(1, 1, n, x, y, k);
}
else if (op == 2) {
cin >> x >> y;
cout << Opt_query(1, 1, n, x, y) << endl;
}
}
return 0;
}
by emo_male_god @ 2023-08-09 19:15:02
啊?我都能直接运行啊?确定是CE不是RE?
by SF_bee @ 2023-08-09 19:19:04
数组爆内存了,尝试使用空间复杂度更低的算法
by Argvchs @ 2023-08-09 19:30:53
@SF_bee 这么小的数组还爆内存??
by SF_bee @ 2023-08-09 19:51:38
我自己试爆了