| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1125850 | _callmelucian | Weirdtree (RMI21_weirdtree) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 3e5 + 5;
struct ITBeats {
private:
vector<ll> sum, hi, secHi, cntHi, lazy;
public:
ITBeats (int sz) : sum(4 * sz), hi(4 * sz), secHi(4 * sz, LLONG_MIN),
cntHi(4 * sz, 1), lazy(4 * sz, LLONG_MIN) {}
private:
void apply (int k, int chmin) {
// cout << "apply " << hi[k] << " " << chmin << "\n";
sum[k] -= (hi[k] - chmin) * cntHi[k];
lazy[k] = hi[k] = chmin;
assert(hi[k] != secHi[k]);
}
void refine (int k) {
sum[k] = sum[k << 1] + sum[k << 1 | 1];
if (hi[k << 1] == hi[k << 1 | 1]) {
hi[k] = hi[k << 1], secHi[k] = max(secHi[k << 1], secHi[k << 1 | 1]);
cntHi[k] = cntHi[k << 1] + cntHi[k << 1 | 1];
}
else if (hi[k << 1] > hi[k << 1 | 1]) {
hi[k] = hi[k << 1], cntHi[k] = cntHi[k << 1];
secHi[k] = max(secHi[k << 1], hi[k << 1 | 1]);
}
else {
hi[k] = hi[k << 1 | 1], cntHi[k] = cntHi[k << 1 | 1];
secHi[k] = max(hi[k << 1], secHi[k << 1 | 1]);
}
assert(hi[k] > secHi[k]);
}
void pushDown (int k, int l, int r) {
if (lazy[k] == LLONG_MIN) return;
int mid = (l + r) >> 1;
update(l, mid, lazy[k], k << 1, l, mid);
update(mid + 1, r, lazy[k], k << 1 | 1, mid + 1, r);
lazy[k] = LLONG_MIN;
}
pl merging (pl a, pl b) {
if (a.first == b.first) return {a.first, max(a.second, b.second)};
if (a.first > b.first) return {a.first, max(a.second, b.first)};
if (a.first < b.first) return {b.first, max(a.first, b.second)};
}
public:
void update (int a, int b, int chmin, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a || chmin >= hi[k]) return;
if (a <= l && r <= b) {
if (secHi[k] < chmin && chmin < hi[k])
return apply(k, chmin), void();
}
pushDown(k, l, r);
int mid = (l + r) >> 1;
update(a, b, chmin, k << 1, l, mid);
update(a, b, chmin, k << 1 | 1, mid + 1, r);
refine(k);
}
void assgn (int pos, int val, int k = 1, int l = 1, int r = mn) {
if (pos < l || r < pos) return;
if (l == r)
return hi[k] = sum[k] = val, secHi[k] = LLONG_MIN, cntHi[k] = 1, void();
pushDown(k, l, r); int mid = (l + r) >> 1;
assgn(pos, val, k << 1, l, mid);
assgn(pos, val, k << 1 | 1, mid + 1, r);
refine(k);
}
ll query (int a, int b, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return sum[k];
pushDown(k, l, r); int mid = (l + r) >> 1;
return query(a, b, k << 1, l, mid) + query(a, b, k << 1 | 1, mid + 1, r);
}
int queryCnt (int a, int b, int hiCur, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) return (hi[k] == hiCur ? cntHi[k] : 0);
pushDown(k, l, r); int mid = (l + r) >> 1;
return queryCnt(a, b, hiCur, k << 1, l, mid) +
queryCnt(a, b, hiCur, k << 1 | 1, mid + 1, r);
}
pl queryMax (int a, int b, int k = 1, int l = 1, int r = mn) {
if (b < l || r < a) return make_pair(LLONG_MIN, LLONG_MIN);
if (a <= l && r <= b) {
assert(hi[k] > secHi[k]);
// cout << "g(" << hi[k] << ") ";
return make_pair(hi[k], secHi[k]);
}
pushDown(k, l, r); int mid = (l + r) >> 1;
return merging(queryMax(a, b, k << 1, l, mid),
queryMax(a, b, k << 1 | 1, mid + 1, r));
}
// find a prefix where cntHi = need
// int walk (int need, int hiCur, int k = 1, int l = 1, int r = mn) {
// if (l == r) return l;
// pushDown(k);
// int mid = (l + r) >> 1, realHi = (hi[k << 1] == hiCur ? cntHi[k << 1] : 0);
// if (realHi < need)
// return walk(need - realHi, hiCur, k << 1 | 1, mid + 1, r);
// return walk(need, hiCur, k << 1, l, mid);
// }
} tree(mn);
void initialize (int _N, int _Q, int h[]) {
for (int i = 1; i <= _N; i++) tree.assgn(i, h[i]);
}
void cut (int l, int r, int k) {
int oldK = k;
while (k > 0) {
ll best, secBest; tie(best, secBest) = tree.queryMax(l, r);
secBest = max(0LL, secBest);
int cntHi = tree.queryCnt(l, r, best);
if (best == 0) return;
// cout << "pre-info " << l << ".." << r << " " << best << " " << secBest << " " << cntHi << " " << k << "\n";
if ((best - secBest) * cntHi <= k) {
k -= (best - secBest) * cntHi;
tree.update(l, r, secBest);
// cout << k - (best - secBest) * cntHi << "\n";
// cout << "change-a " << l << ".." << r << " " << best << " -> " << secBest << "\n";
}
else {
ll fully = k / cntHi, cur = best - fully;
k -= fully * cntHi, tree.update(l, r, cur);
// cout << "change-b " << l << ".." << r << " " << best << " -> " << cur << "\n";
if (k) {
int need = tree.queryCnt(1, l - 1, cur) + k, pos = l - 1;
for (int step = (r - l + 1); step > 0; step >>= 1) {
while (pos + step <= r && tree.queryCnt(l, pos + step, cur) < k) pos += step;
}
pos++;
tree.update(l, min(pos, r), cur - 1), k = 0;
// cout << "change-c " << need << " " << l << ".." << pos << " " << cur << " -> " << cur - 1 << "\n";
}
}
// if (oldK == k) {
// cout << "f " << oldK << " " << k << "\n";
// exit(0);
// }
// oldK = k;
}
}
void magic (int i, int x) {
tree.assgn(i, x);
}
ll inspect (int l, int r) {
return tree.query(l, r, 1);
}
#ifdef LOCAL
int init[mn];
int main()
{
freopen("WEIRD.inp", "r", stdin);
freopen("WEIRD.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> init[i];
initialize(n, q, init);
while (q--) {
int type; cin >> type;
if (type == 1) {
int l, r, k; cin >> l >> r >> k;
cut(l, r, k);
}
else if (type == 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