#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
#define fi first
#define se second
const int MAX = 2e5 + 5;
const int BLOCK = sqrt(MAX);
const int INF = 1e9 + 1;
struct node {
long long sum;
int ma1, ma2, fr, lazy;
node(long long sum = 0, int ma1 = 0, int ma2 = 0, int fr = 0, int lazy = INF) : sum(sum), ma1(ma1), ma2(ma2), fr(fr), lazy(lazy) {}
} infor[BLOCk + 5] ;
int n, h[MAX];
int id_block(int pos) {
return (pos - 1) / BLOCK;
}
int begin_block(int id) {
return id * BLOCK;
}
int end_block(int id) {
return min((id + 1) * BLOCK, n) - 1;
}
void build_block(int id) {
int l = begin_block(id), r = end_block(id);
infor[id].ma1 = infor[id].ma2 = infor[id].fr = infor[id].sum = 0;
for (int i = l; i <= r; ++i) {
h[i] = min(h[i], infor[id].lazy);
infor[id].sum += h[i];
if(infor[id].ma1 < h[i]) {
infor[id].ma2 = infor[id].ma1;
infor[id].ma1 = h[i];
infor[id].fr = 1;
} else {
if(h[i] == infor[id].ma1) infor[id].fr++;
infor[id].ma2 = max(infor[id].ma2, h[i]);
}
}
infor[id].lazy = INF;
}
void initialise(int _n, int q, int _h[]) {
n = _n;
for (int i = 0; i < n; ++i) h[i] = _h[i + 1];
for (int i = 0; i < n; i += BLOCK) {
build_block(i / BLOCK);
}
}
node get(int l, int r) {
node res;
for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
if(res.ma1 < h[i]) {
res.ma2 = res.ma1;
res.ma1 = h[i];
res.fr = 1;
} else {
if(res.ma1 == h[i]) res.fr++;
res.ma2 = max(res.ma2, h[i]);
}
res.sum += h[i];
}
if(id_block(l) != id_block(r)) {
for (int i = begin_block(id_block(r)); i <= r; ++i) {
if(res.ma1 < h[i]) {
res.ma2 = res.ma1;
res.ma1 = h[i];
res.fr = 1;
} else {
if(res.ma1 == h[i]) res.fr++;
res.ma2 = max(res.ma2, h[i]);
}
res.sum += h[i];
}
}
for (int i = id_block(l); ++i < id_block(r);) {
if(res.ma1 < infor[i].ma1) {
res.ma2 = res.ma1;
res.ma1 = infor[i].ma1;
res.fr = infor[i].fr;
} else {
if(res.ma1 == infor[i].ma1) res.fr += infor[i].fr;
res.ma2 = max(res.ma2, infor[i].ma1);
}
res.sum += infor[i].sum;
}
return res;
}
void cut(int l, int r, int k) {
l--, r--;
while(k > 0) {
node res = get(l, r);
if(res.ma1 == 0) break;
long long tmp = 1LL * res.fr * (res.ma1 - res.ma2);
if(k >= tmp) {
k -= tmp;
for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
h[i] = min(h[i], res.ma2);
}
build_block(id_block(l));
if(id_block(l) != id_block(r)) {
for (int i = begin_block(id_block(r)); i <= r; ++i) {
h[i] = min(h[i], res.ma2);
}
build_block(id_block(r));
}
for (int i = id_block(l); ++i < id_block(r);) {
if(infor[i].ma1 == res.ma1) {
infor[i].lazy = res.ma2;
infor[i].ma1 = res.ma2;
infor[i].sum -= 1LL * infor[i].fr * (res.ma1 - res.ma2);
}
if(infor[i].ma1 == infor[i].ma2) build_block(i);
}
} else {
int tmp =
k = 0;
for (int i = l; i <= min(r, end_block(id_block(l))); ++i) {
}
}
}
}
void magic(int i, int x) {
i--;
build_block(id_block(i));
h[i] = x;
build_block(id_block(i));
}
long long inspect(int l, int r) {
return get(l - 1, r - 1).sum;
}
#ifdef LOCAL
#include <iostream>
using namespace std;
int main() {
int N, Q;
cin >> N >> Q;
int h[N + 1];
for (int i = 1; i <= N; ++i) cin >> h[i];
initialise(N, Q, h);
for (int i = 1; i <= Q; ++i) {
int t;
cin >> t;
if (t == 1) {
int l, r, k;
cin >> l >> r >> k;
cut(l, r, k);
} else if (t == 2) {
int i, x;
cin >> i >> x;
magic(i, x);
} else {
int l, r;
cin >> l >> r;
cout << inspect(l, r) << '\n';
}
}
return 0;
}
#endif // LOCAL
// Dream it. Wish it. Do it.
Compilation message
weirdtree.cpp:17:9: error: 'BLOCk' was not declared in this scope; did you mean 'BLOCK'?
17 | } infor[BLOCk + 5] ;
| ^~~~~
| BLOCK
weirdtree.cpp: In function 'void build_block(int)':
weirdtree.cpp:35:5: error: 'infor' was not declared in this scope
35 | infor[id].ma1 = infor[id].ma2 = infor[id].fr = infor[id].sum = 0;
| ^~~~~
weirdtree.cpp: In function 'node get(int, int)':
weirdtree.cpp:88:22: error: 'infor' was not declared in this scope
88 | if(res.ma1 < infor[i].ma1) {
| ^~~~~
weirdtree.cpp:96:20: error: 'infor' was not declared in this scope
96 | res.sum += infor[i].sum;
| ^~~~~
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:122:20: error: 'infor' was not declared in this scope
122 | if(infor[i].ma1 == res.ma1) {
| ^~~~~
weirdtree.cpp:128:20: error: 'infor' was not declared in this scope
128 | if(infor[i].ma1 == infor[i].ma2) build_block(i);
| ^~~~~
weirdtree.cpp:131:17: warning: unused variable 'tmp' [-Wunused-variable]
131 | int tmp =
| ^~~
