#include "weirdtree.h"
#include <bits/stdc++.h>
using ll = long long;
const int NMAX(300005), INF(1000000005);
int v[NMAX], n;
struct node{
ll sum;
int max1, max2, fr1;
node operator+(node b){
node rez;
if(max1 < b.max1){
rez.max1 = b.max1, rez.fr1 = b.fr1;
rez.max2 = max1;
}
else if(max1 > b.max1){
rez.max1 = max1, rez.fr1 = fr1;
rez.max2 = b.max1;
}
else {
rez.max1 = max1;
rez.fr1 = fr1 + b.fr1;
rez.max2 = max(max2, b.max2);
}
rez.max2 = max(rez.max2, max(max2, b.max2));
rez.sum = sum + b.sum;
return rez;
}
}NUP={0, 0, -INF, 0};
struct SegTree{
vector<node> Arb;
inline void init(int n){
int put = 1;
while(put <= n)
put <<= 1;
put <<= 1;
Arb.resize(put);
}
inline void build(int nod, int st, int dr){
if(st == dr){
Arb[nod].max1 = Arb[nod].sum = v[st];
Arb[nod].max2 = -INF;
Arb[nod].fr1 = 1;
return;
}
int mij = (st + dr) / 2;
build(2 * nod, st, mij);
build(2 * nod + 1, mij + 1, dr);
Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
}
inline void UpdateNod(int nod, int unde){
Arb[nod].sum -= 1LL * (Arb[nod].max1 - unde) * Arb[nod].fr1;
Arb[nod].max1 = unde;
}
inline void push(int nod){
if(Arb[2 * nod].max1 > Arb[nod].max1)
UpdateNod(2 * nod, Arb[nod].max1);
if(Arb[2 * nod + 1].max1 > Arb[nod].max1)
UpdateNod(2 * nod + 1, Arb[nod].max1);
}
inline void Update(int nod, int st, int dr, int a, int b, int &extra, int capat){
if(Arb[nod].max1 <= capat - (extra > 0))
return;
if(a <= st && dr <= b && (extra == 0 || extra >= Arb[nod].fr1) && capat - (extra > 0) > Arb[nod].max2){
UpdateNod(nod, capat - (extra > 0));
if(extra > 0)
extra -= Arb[nod].fr1;
return;
}
push(nod);
int mij = (st + dr) / 2;
if(a <= mij)
Update(2 * nod, st, mij, a, b, extra, capat);
if(b > mij)
Update(2 * nod + 1, mij + 1, dr, a, b, extra, capat);
Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
}
inline node Unify(int nod, int st, int dr, int a, int b){
if(a <= st && dr <= b)
return Arb[nod];
int mij = (st + dr) / 2;
node rez1 = NUP, rez2 = NUP;
if(a <= mij)
rez1 = Unify(2 * nod, st, mij, a, b);
if(b > mij)
rez2 = Unify(2 * nod + 1, mij + 1, dr, a, b);
return rez1 + rez2;
}
inline void update2(int nod, int st, int dr, int poz, int val){
if(st == dr){
Arb[nod].max1 = Arb[nod].sum = val, Arb[nod].fr1 = 1;
Arb[nod].max2 = -INF;
return;
}
push(nod);
int mij = (st + dr) / 2;
if(poz <= mij)
update2(2 * nod, st, mij, poz, val);
else update2(2 * nod + 1, mij + 1, dr, poz, val);
Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
}
}Sol;
void initialise(int N, int Q, int h[]) {
n = N;
for(int i = 1; i <= N; ++i)
v[i] = h[i];
Sol.init(N);
Sol.build(1, 1, N);
}
void cut(int l, int r, int k) {
while(k > 0){
auto p = Sol.Unify(1, 1, n, l, r);
if(p.max1 == 0)
return;
ll nrP = 1LL * p.fr1 * (p.max1 - p.max2);
if(nrP <= k){
int val = 0;
Sol.Update(1, 1, n, l, r, val, p.max2);
k -= nrP;
}
else {
int val = k % p.fr1;
Sol.Update(1, 1, n, l, r, val, p.max1 - k / p.fr1);
k = 0;
}
}
}
void magic(int i, int x) {
Sol.update2(1, 1, n, i, x);
}
long long int inspect(int l, int r) {
auto p = Sol.Unify(1, 1, n, l, r);
return p.sum;
}
Compilation message
weirdtree.cpp: In member function 'node node::operator+(node)':
weirdtree.cpp:22:24: error: 'max' was not declared in this scope; did you mean 'std::max'?
22 | rez.max2 = max(max2, b.max2);
| ^~~
| std::max
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from weirdtree.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: 'std::max' declared here
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
weirdtree.cpp:24:34: error: 'max' was not declared in this scope; did you mean 'std::max'?
24 | rez.max2 = max(rez.max2, max(max2, b.max2));
| ^~~
| std::max
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from weirdtree.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: 'std::max' declared here
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
weirdtree.cpp:24:20: error: 'max' was not declared in this scope; did you mean 'std::max'?
24 | rez.max2 = max(rez.max2, max(max2, b.max2));
| ^~~
| std::max
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from weirdtree.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: 'std::max' declared here
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
weirdtree.cpp: At global scope:
weirdtree.cpp:31:5: error: 'vector' does not name a type
31 | vector<node> Arb;
| ^~~~~~
weirdtree.cpp: In member function 'void SegTree::init(int)':
weirdtree.cpp:37:9: error: 'Arb' was not declared in this scope
37 | Arb.resize(put);
| ^~~
weirdtree.cpp: In member function 'void SegTree::build(int, int, int)':
weirdtree.cpp:41:13: error: 'Arb' was not declared in this scope
41 | Arb[nod].max1 = Arb[nod].sum = v[st];
| ^~~
weirdtree.cpp:49:9: error: 'Arb' was not declared in this scope
49 | Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
| ^~~
weirdtree.cpp: In member function 'void SegTree::UpdateNod(int, int)':
weirdtree.cpp:52:9: error: 'Arb' was not declared in this scope
52 | Arb[nod].sum -= 1LL * (Arb[nod].max1 - unde) * Arb[nod].fr1;
| ^~~
weirdtree.cpp: In member function 'void SegTree::push(int)':
weirdtree.cpp:56:12: error: 'Arb' was not declared in this scope
56 | if(Arb[2 * nod].max1 > Arb[nod].max1)
| ^~~
weirdtree.cpp:58:12: error: 'Arb' was not declared in this scope
58 | if(Arb[2 * nod + 1].max1 > Arb[nod].max1)
| ^~~
weirdtree.cpp: In member function 'void SegTree::Update(int, int, int, int, int, int&, int)':
weirdtree.cpp:62:12: error: 'Arb' was not declared in this scope
62 | if(Arb[nod].max1 <= capat - (extra > 0))
| ^~~
weirdtree.cpp:64:58: error: 'Arb' was not declared in this scope
64 | if(a <= st && dr <= b && (extra == 0 || extra >= Arb[nod].fr1) && capat - (extra > 0) > Arb[nod].max2){
| ^~~
weirdtree.cpp:76:9: error: 'Arb' was not declared in this scope
76 | Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
| ^~~
weirdtree.cpp: In member function 'node SegTree::Unify(int, int, int, int, int)':
weirdtree.cpp:80:20: error: 'Arb' was not declared in this scope
80 | return Arb[nod];
| ^~~
weirdtree.cpp: In member function 'void SegTree::update2(int, int, int, int, int)':
weirdtree.cpp:91:13: error: 'Arb' was not declared in this scope
91 | Arb[nod].max1 = Arb[nod].sum = val, Arb[nod].fr1 = 1;
| ^~~
weirdtree.cpp:100:9: error: 'Arb' was not declared in this scope
100 | Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
| ^~~
