#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "weirdtree.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
struct segtree_beats {
struct node {
int ma1, ma2, freq;
ll sum;
int abbassa;
node(int a = -1, int b = -1, int c = 1, ll d = 0, int e = -1) {
ma1 = a;
ma2 = b;
freq = c;
sum = d;
abbassa = e;
}
};
static const int dim = 1 << 17;
vector<node> s = vector<node>(2 * dim);
void sist(int pos, int l, int r) {
if (s[pos].abbassa == -1) return;
if (s[pos].ma1 <= s[pos].abbassa) {
s[pos].abbassa = -1;
return;
}
s[pos].sum -= (ll)(s[pos].ma1 - s[pos].abbassa) * s[pos].freq;
s[pos].ma1 = s[pos].abbassa;
if (pos < dim) {
if (s[2 * pos].abbassa == -1 || s[2 * pos].abbassa > s[pos].abbassa) s[2 * pos].abbassa = s[pos].abbassa;
if (s[2 * pos + 1].abbassa == -1 || s[2 * pos + 1].abbassa > s[pos].abbassa) s[2 * pos + 1].abbassa = s[pos].abbassa;
}
s[pos].abbassa = -1;
}
void recalc(int pos) {
if (s[2 * pos].ma1 > s[2 * pos + 1].ma1) {
s[pos].ma1 = s[2 * pos].ma1;
s[pos].freq = s[2 * pos].freq;
s[pos].ma2 = max(s[2 * pos].ma2, s[2 * pos + 1].ma1);
} else if (s[2 * pos].ma1 < s[2 * pos + 1].ma1) {
s[pos].ma1 = s[2 * pos + 1].ma1;
s[pos].freq = s[2 * pos + 1].freq;
s[pos].ma2 = max(s[2 * pos].ma1, s[2 * pos + 1].ma2);
} else {
s[pos].ma1 = s[2 * pos].ma1;
s[pos].freq = s[2 * pos].freq + s[2 * pos + 1].freq;
s[pos].ma2 = max(s[2 * pos].ma2, s[2 * pos + 1].ma2);
}
s[pos].sum = s[2 * pos].sum + s[2 * pos + 1].sum;
}
void setta(int pos, int l, int r, int p, int val) {
sist(pos, l, r);
if (p < l || r < p) return;
if (l == r) {
s[pos] = {val, -1, 1, val, -1};
return;
}
int m = (l + r) / 2;
setta(2 * pos, l, m, p, val);
setta(2 * pos + 1, m + 1, r, p, val);
recalc(pos);
}
void setta(int p, int val) { setta(1, 0, dim - 1, p, val); }
int abbassa(int pos, int l, int r, int a, int b, int k, bool apply) {
sist(pos, l, r);
if (b < l || r < a) return 0;
if (s[pos].ma1 <= k) return 0;
if (a <= l && r <= b && s[pos].ma2 < k) {
ll tot = (ll)(s[pos].ma1 - k) * s[pos].freq;
if (apply) {
s[pos].abbassa = k;
sist(pos, l, r);
}
tot = min(tot, (int)2e9);
return tot;
}
int m = (l + r) / 2;
int tot = abbassa(2 * pos, l, m, a, b, k, apply) + abbassa(2 * pos + 1, m + 1, r, a, b, k, apply);
recalc(pos);
tot = min(tot, (int)2e9);
return tot;
}
int abbassa(int a, int b, int k, bool apply) { return abbassa(1, 0, dim - 1, a, b, k, apply); }
int abbassa1(int pos, int l, int r, int a, int b, int k, int count) {
sist(pos, l, r);
if (count == 0) return 0;
if (b < l || r < a) return 0;
if (s[pos].ma1 <= k) return 0;
if (a <= l && r <= b && s[pos].ma2 < k && (s[pos].ma1 - k) * s[pos].freq <= count) {
ll tot = (ll)(s[pos].ma1 - k) * s[pos].freq;
tot = min(tot, (int)2e9);
s[pos].abbassa = k;
sist(pos, l, r);
return tot;
}
int m = (l + r) / 2;
int tot = abbassa1(2 * pos, l, m, a, b, k, count);
count -= tot;
tot += abbassa1(2 * pos + 1, m + 1, r, a, b, k, count);
tot = min(tot, (int)2e9);
recalc(pos);
return tot;
}
int abbassa1(int a, int b, int k, int count) { return abbassa1(1, 0, dim - 1, a, b, k, count); }
ll query(int pos, int l, int r, int a, int b) {
sist(pos, l, r);
if (b < l || r < a) return 0;
if (a <= l && r <= b) return s[pos].sum;
int m = (l + r) / 2;
ll tot = query(2 * pos, l, m, a, b) + query(2 * pos + 1, m + 1, r, a, b);
return tot;
}
ll query(int a, int b) { return query(1, 0, dim - 1, a, b); }
} seg;
int N;
void dbg() {
// for (int i = 0; i < N; i++) cout << seg.query(i, i) << " ";
// cout << endl;
}
void initialise(signed n, signed Q, signed h[]) {
N = n;
for (int i = 0; i < N; i++) {
seg.setta(i, h[i + 1]);
}
dbg();
}
void cut(signed l, signed r, signed k) {
l--;
r--;
int x = 0, y = 1e9 + 10;
while (x < y) {
int m = (x + y + 1) / 2;
int q = seg.abbassa(l, r, m, 0);
if (q < k)
y = m - 1;
else
x = m;
}
k -= seg.abbassa(l, r, x + 1, 1);
// cout << x << " " << k << endl;
// dbg();
seg.abbassa1(l, r, x, k);
dbg();
}
void magic(signed i, signed x) {
i--;
seg.setta(i, x);
dbg();
}
ll inspect(signed l, signed r) {
l--;
r--;
return seg.query(l, r);
}
Compilation message
weirdtree.cpp: In member function 'int segtree_beats::abbassa(int, int, int, int, int, int, bool)':
weirdtree.cpp:79:36: error: no matching function for call to 'min(long long int&, int)'
79 | tot = min(tot, (int)2e9);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from weirdtree.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
weirdtree.cpp:79:36: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
79 | tot = min(tot, (int)2e9);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from weirdtree.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
weirdtree.cpp:79:36: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
79 | tot = min(tot, (int)2e9);
| ^
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:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
weirdtree.cpp:79:36: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
79 | tot = min(tot, (int)2e9);
| ^
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:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
weirdtree.cpp:79:36: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
79 | tot = min(tot, (int)2e9);
| ^
weirdtree.cpp: In member function 'int segtree_beats::abbassa1(int, int, int, int, int, int, int)':
weirdtree.cpp:97:36: error: no matching function for call to 'min(long long int&, int)'
97 | tot = min(tot, (int)2e9);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from weirdtree.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
weirdtree.cpp:97:36: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
97 | tot = min(tot, (int)2e9);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from weirdtree.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
weirdtree.cpp:97:36: note: deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
97 | tot = min(tot, (int)2e9);
| ^
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:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
3468 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: template argument deduction/substitution failed:
weirdtree.cpp:97:36: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
97 | tot = min(tot, (int)2e9);
| ^
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:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
3474 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: template argument deduction/substitution failed:
weirdtree.cpp:97:36: note: mismatched types 'std::initializer_list<_Tp>' and 'long long int'
97 | tot = min(tot, (int)2e9);
| ^
