#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
void maxSelf(int &x, int y) {
if (x < y) {
x = y;
}
}
struct node {
int64_t sum;
int max1, cntMax, max2;
node operator + (const node &rhs) const {
node ans;
ans.sum = sum + rhs.sum;
ans.max1 = max(max1, rhs.max1);
ans.max2 = max(max2, rhs.max2);
if (max1 < rhs.max1) {
ans.cntMax = rhs.cntMax;
maxSelf(ans.max2, max1);
} else if (rhs.max1 < max1) {
ans.cntMax = cntMax;
maxSelf(ans.max2, rhs.max1);
} else {
ans.cntMax = cntMax + rhs.cntMax;
}
return ans;
}
} NIL{0, 0, 0, -INF};
struct ST {
int n, dim = 1;
vector<node> t;
ST(int N) : n(N) {
while (dim < n) {
dim *= 2;
}
dim *= 2;
t.resize(dim);
}
void setVal(int x, int v) {
t[x].sum = t[x].max1 = v;
t[x].cntMax = 1;
t[x].max2 = -INF;
}
void build(int x, int lx, int rx) {
if (lx == rx) {
int v;
cin >> v;
setVal(x, v);
return;
}
int mid = (lx + rx) / 2;
build(x * 2, lx, mid);
build(x * 2 + 1, mid + 1, rx);
t[x] = t[x * 2] + t[x * 2 + 1];
}
void updateNode(int x, int v) {
t[x].sum += (int64_t)(v - t[x].max1) * t[x].cntMax;
t[x].max1 = v;
}
void push(int x) {
for (int i = 0; i < 2; ++i) {
int son = x * 2 + i;
if (dim <= son) {
return;
}
if (t[x].max1 < t[son].max1) {
updateNode(son, t[x].max1);
}
}
}
void update(int x, int lx, int rx, int st, int dr, int &extra, int v) {
if (t[x].max1 <= v - (extra > 0)) {
return;
}
if (st <= lx && rx <= dr && t[x].max2 < v - (extra > 0) && (extra == 0 || extra >= t[x].cntMax)) {
updateNode(x, v - (extra > 0));
if (extra > 0) {
extra -= t[x].cntMax;
}
return;
}
push(x);
int mid = (lx + rx) / 2;
if (st <= mid) {
update(x * 2, lx, mid, st, dr, extra, v);
}
if (mid < dr) {
update(x * 2 + 1, mid + 1, rx, st, dr, extra, v);
}
t[x] = t[x * 2] + t[x * 2 + 1];
}
void update(int st, int dr, int extra, int v) {
update(1, 1, n, st, dr, extra, v);
}
void cut(int st, int dr, int k) {
while (k > 0) {
node ans = query(st, dr);
if (ans.max1 == 0) {
return;
}
int64_t cutMax = (int64_t)ans.cntMax * (ans.max1 - ans.max2);
if (cutMax <= k) {
update(st, dr, 0, ans.max2);
k -= cutMax;
} else {
update(st, dr, k % ans.cntMax, ans.max1 - k / ans.cntMax);
k = 0;
}
}
}
void setPos(int x, int lx, int rx, int pos, int v) {
if (lx == rx) {
setVal(x, v);
return;
}
push(x);
int mid = (lx + rx) / 2;
if (pos <= mid) {
setPos(x * 2, lx, mid, pos, v);
} else {
setPos(x * 2 + 1, mid + 1, rx, pos, v);
}
t[x] = t[x * 2] + t[x * 2 + 1];
}
void setPos(int pos, int v) {
setPos(1, 1, n, pos, v);
}
node query(int x, int lx, int rx, int st, int dr) {
if (st <= lx && rx <= dr) {
return t[x];
}
push(x);
int mid = (lx + rx) / 2;
node left = NIL, right = NIL;
if (st <= mid) {
left = query(x * 2, lx, mid, st, dr);
}
if (mid < dr) {
right = query(x * 2 + 1, mid + 1, rx, st, dr);
}
return left + right;
}
node query(int st, int dr) {
return query(1, 1, n, st, dr);
}
};
void testCase() {
int n, q;
cin >> n >> q;
ST t(n);
t.build(1, 1, n);
for (int i = 0; i < q; ++i) {
char op;
cin >> op;
if (op == '1') {
int l, r, k;
cin >> l >> r >> k;
t.cut(l, r, k);
} else if (op == '2') {
int pos, v;
cin >> pos >> v;
t.setPos(pos, v);
} else {
int l, r;
cin >> l >> r;
cout << t.query(l, r).sum << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 0; tc < tests; ++tc) {
testCase();
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cceYJ0ph.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc7Dlr9h.o:weirdtree.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cceYJ0ph.o: in function `main':
grader.cpp:(.text.startup+0xe2): undefined reference to `initialise(int, int, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x122): undefined reference to `inspect(int, int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x263): undefined reference to `magic(int, int)'
/usr/bin/ld: grader.cpp:(.text.startup+0x28e): undefined reference to `cut(int, int, int)'
collect2: error: ld returned 1 exit status
