#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
typedef long long ll;
#define int ll
const int N = (int) 3e5 + 7;
int a[N];
int n, q;
struct Node {
int max1;
int max2;
int cnt;
ll sum;
};
Node operator + (const Node &a, const Node &b) {
Node aux;
aux.sum = a.sum + b.sum;
if (a.max1 == b.max1) {
aux.max1 = a.max1;
aux.cnt = a.cnt + b.cnt;
aux.max2 = max(a.max2, b.max2);
} else if (a.max1 < b.max1) {
aux.max1 = b.max1;
aux.cnt = b.cnt;
aux.max2 = max(a.max1, b.max2);
} else {
aux.max1 = a.max1;
aux.cnt = a.cnt;
aux.max2 = max(b.max1, a.max2);
}
return aux;
}
Node segt[4 * N];
void baga(int v, int val) {
if (segt[v].max1 <= val) return;
segt[v].sum -= (ll)segt[v].max1 * segt[v].cnt;
segt[v].max1 = val;
segt[v].sum += (ll)segt[v].max1 * segt[v].cnt;
}
void push(int v, int tl, int tr) {
if (tl < tr) {
int tm = (tl + tr) / 2;
baga(2 * v, segt[v].max1);
baga(2 * v + 1, segt[v].max1);
}
}
void build(int v, int tl, int tr) {
if (tl == tr) {
segt[v] = {a[tl], 0, 1, a[tl]};
} else {
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
segt[v] = segt[2 * v] + segt[2 * v + 1];
}
}
void update(int v, int tl, int tr, int x, int y, int val) {
push(v, tl, tr);
if (segt[v].max1 <= val) return;
if (x <= tl && tr <= y && segt[v].max2 < val) {
baga(v, val);
return;
}
int tm = (tl + tr) / 2;
if (x <= tm) {
update(2 * v, tl, tm, x, min(tm, y), val);
}
if (tm + 1 <= y) {
update(2 * v + 1, tm + 1, tr, max(x, tm + 1), y, val);
}
segt[v] = segt[2 * v] + segt[2 * v + 1];
}
void update2(int v, int tl, int tr, int pos, int val) {
push(v, tl, tr);
if (tl == tr) {
segt[v] = {val, 0, 1, val};
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
update2(2 * v, tl, tm, pos, val);
} else {
update2(2 * v + 1, tm + 1, tr, pos, val);
}
push(2 * v, tl, tm);
push(2 * v + 1, tm + 1, tr);
segt[v] = segt[2 * v] + segt[2 * v + 1];
}
Node query(int v, int tl, int tr, int x, int y) {
push(v, tl, tr);
if (x <= tl && tr <= y) {
return segt[v];
}
int tm = (tl + tr) / 2;
if (x <= tm && y <= tm) {
return query(2 * v, tl, tm, x, y);
} else if (tm + 1 <= x && tm + 1 <= y) {
return query(2 * v + 1, tm + 1, tr, x, y);
} else {
return query(2 * v, tl, tm, x, tm) + query(2 * v + 1, tm + 1, tr, tm + 1, y);
}
}
void initialise(int N, int Q, int h[]) {
n = N;
q = Q;
for (int i = 1; i <= n; i++) {
a[i] = h[i];
}
build(1, 1, n);
}
void cut(int l, int r, int k) {
while (k > 0) {
Node res = query(1, 1, n, l, r);
if (res.max1 == 0) {
break;
}
if ((ll)(res.max1 - res.max2) * res.cnt <= k) {
k -= (ll)(res.max1 - res.max2) * res.cnt;
update(1, 1, n, l, r, res.max2);
continue;
}
int full = k / res.cnt;
int partial = k % res.cnt;
if (full > 0) update(1, 1, n, l, r, res.max1 - full);
if (partial > 0) {
int low = l, high = r, sol = 0;
while (low <= high) {
int mid = (low + high) / 2;
Node aux = query(1, 1, n, l, mid);
if (aux.max1 == res.max1 - full && aux.cnt == partial) {
sol = mid;
break;
}
if (aux.max1 < res.max1 - full || aux.cnt < partial) {
low = mid + 1;
} else {
high = mid - 1;
}
}
update(1, 1, n, l, sol, res.max1 - full - 1);
}
break;
}
}
void magic(int pos, int val) {
update2(1, 1, n, pos, val);
}
ll inspect(int l, int r) {
Node res = query(1, 1, n, l, r);
return res.sum;
}
Compilation message
weirdtree.cpp: In function 'void push(ll, ll, ll)':
weirdtree.cpp:49:9: warning: unused variable 'tm' [-Wunused-variable]
49 | int tm = (tl + tr) / 2;
| ^~
/usr/bin/ld: /tmp/ccP0PiGs.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
