Saka_Noa @ 2023-09-21 15:03:12
#include<bits/stdc++.h>
using namespace std;
#define ls(x) FHQ[x].Son[0]
#define rs(x) FHQ[x].Son[1]
#define vl(x) FHQ[x].val
#define si(x) FHQ[x].si
#define sm(x) FHQ[x].sum
#define tg(x) FHQ[x].tag
#define rr int r1 = 0, int r2 = 0, int r3 = 0
#define rp(i, a, b) for(int i = a;i <= b;i++)
const int N = 1e5 + 50;
struct Tree{
int pri, Son[2], si;
long long val, sum, tag;
} FHQ[N];
int cnt, root, x, n, m, opt, l, r;
int new_node(int v) {
FHQ[++cnt] = Tree{rand(), {0, 0}, 1, v, v, 0};
return cnt;
}
void update(int x) {
si(x) = si(ls(x)) + si(rs(x)) + 1;
sm(x) = sm(ls(x)) + sm(rs(x));
}
void pushdown(int x) {
if(!tg(x)) return;
sm(ls(x)) += si(ls(x)) * tg(x);
sm(rs(x)) += si(rs(x)) * tg(x);
vl(ls(x)) += tg(x);
vl(rs(x)) += tg(x);
tg(ls(x)) += tg(x);
tg(rs(x)) += tg(x);
tg(x) = 0;
}
void split(int x, int k, int &a, int &b) {
if(!x) return (void)(a = b = 0);
pushdown(x);
if(k <= si(ls(x))) {
b = x;
split(ls(x), k, a, ls(x));
} else {
a = x;
k -= si(ls(x)) + 1;
split(rs(x), k, rs(x), b);
}
update(x);
}
int merge(int x, int y) {
if(!x || !y) return x + y;
pushdown(x);
pushdown(y);
if(FHQ[x].pri < FHQ[x].pri) {
rs(x) = merge(rs(x), y);
update(x);
return x;
} else {
ls(y) = merge(x, ls(y));
update(y);
return y;
}
}
void insert(long long v) {
root = merge(root, new_node(v));
}
void modify(int x, int y, long long v, rr) {
split(root, x - 1, r1, r2);
split(r2, y - x + 1, r2, r3);
tg(r2) += v;
vl(r2) += v;
sm(r2) += v * si(r2);
root = merge(r1, merge(r2, r3));
}
long long query(int x, int y, rr) {
split(root, x - 1, r1, r2);
split(r2, y - x + 1, r2, r3);
long long ans = sm(r2);
root = merge(r1, merge(r2, r3));
return ans;
}
int main() {
srand(time(0));
scanf("%d %d", &n, &m);
rp(i, 1, n) scanf("%d", &x), insert(x);
rp(i, 1, m) {
scanf("%d %d %d", &opt, &l, &r);
if(opt == 1) {
scanf("%d", &x);
modify(l, r, x);
} else
printf("%lld\n", query(l, r));
}
return 0;
}
by LgxTpre @ 2023-09-21 15:12:51
@Saka_Noa 先说个小错误,你的 52 行在干什么
by LgxTpre @ 2023-09-21 15:14:47
@Saka_Noa 第 23 行
sm(x) = sm(ls(x)) + sm(rs(x)) + vl(x);
by Saka_Noa @ 2023-09-21 15:27:06
@LgxTpre 感激不尽,调过了