// File B.cpp created on 08.08.2025 at 11:52:11
#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
constexpr int max_N = int(1E5) + 5;
int N;
int A[max_N];
struct Info {
int l, r;
std::vector<int> pntl;
std::vector<int> frql;
std::vector<i64> suml;
std::vector<int> pntr;
std::vector<int> frqr;
std::vector<i64> sumr;
Info() {}
Info(int x) {
l = r = x;
pntl = {x};
frql = {1};
suml = {A[x]};
pntr = {x};
frqr = {1};
sumr = {A[x]};
}
} tree[max_N << 1];
void clear(std::vector<int>& pnt, std::vector<int>& frq, std::vector<i64>& sum) {
std::vector<int> npnt;
std::vector<int> nfrq;
std::vector<i64> nsum;
for (int i = 0; i < int(pnt.size()); ++i) {
if (frq[i]) {
npnt.emplace_back(pnt[i]);
nfrq.emplace_back(frq[i]);
nsum.emplace_back(sum[i]);
}
}
pnt = std::move(npnt);
frq = std::move(nfrq);
sum = std::move(nsum);
}
Info operator+ (const Info& lhs, const Info& rhs) {
Info res;
res.l = lhs.l;
res.r = rhs.r;
{
int sizl = int(lhs.pntl.size());
int sizr = int(rhs.pntl.size());
int n = sizl + sizr;
res.pntl.insert(res.pntl.end(), lhs.pntl.begin(), lhs.pntl.end());
res.pntl.insert(res.pntl.end(), rhs.pntl.begin(), rhs.pntl.end());
res.frql.resize(n);
res.suml.resize(n);
for (int i = 0; i < n; ++i) {
if (i < sizl) {
res.suml[i] = lhs.suml[i];
} else {
res.suml[i] = lhs.suml.back() + rhs.suml[i - sizl];
}
}
{ // Case 1: sol childimin sola yapisik ama saga yapisik olmayani ekle
for (int i = 0; i < sizl - 1; ++i) {
res.frql[i] += lhs.frql[i];
}
}
{ // Case 2: sol childimin saga yapisik olanlari sola ve saga buyutup ekle
int m = int(lhs.pntr.size());
int l = m, r = -1;
for (int i = m - 1; i >= 0; --i) {
l = std::min(l, i);
while (true) {
i64 sum = lhs.sumr[l] + (r == -1 ? 0 : rhs.suml[r]);
if (r != sizr - 1 && sum >= A[r == -1 ? rhs.l : (rhs.pntl[r] + 1)]) {
r++;
continue;
}
if (l != 0 && sum >= A[lhs.pntr[l] - 1]) {
l--;
continue;
}
break;
}
if (l == 0) {
res.frql[sizl + r] += lhs.frqr[i];
}
}
}
{ // Case 3: sag childimin sola yapisik kaplayanlari buyutup eger sola yapisirlarsa ekle
int m = int(lhs.pntr.size());
int l = m, r = -1;
for (int i = 0; i < sizr; ++i) {
r = std::max(r, i);
while (true) {
i64 sum = (l == m ? 0 : lhs.sumr[l]) + rhs.suml[r];
if (r != sizr - 1 && A[rhs.pntl[r] + 1] <= sum) {
r++;
continue;
}
if (l != 0 && A[l == m ? lhs.r : (lhs.pntr[l] - 1)] <= sum) {
l--;
continue;
}
break;
}
if (l == 0) {
res.frql[sizl + r] += rhs.frql[i];
}
}
}
}
{
int sizl = int(lhs.pntr.size());
int sizr = int(rhs.pntr.size());
int n = sizl + sizr;
res.pntr.insert(res.pntr.end(), lhs.pntr.begin(), lhs.pntr.end());
res.pntr.insert(res.pntr.end(), rhs.pntr.begin(), rhs.pntr.end());
res.frqr.resize(n);
res.sumr.resize(n);
for (int i = 0; i < n; ++i) {
if (i < sizl) {
res.sumr[i] = lhs.sumr[i] + rhs.sumr[0];
} else {
res.sumr[i] = rhs.sumr[i - sizl];
}
}
{ // Case 1: sag childimin saga yapisik ama sola yapisik olmayani ekle
for (int i = 1; i < sizr; ++i) {
res.frqr[sizl + i] += rhs.frqr[i];
}
}
{ // Case 2: sag childimin sola yapisik olanlari sola ve saga buyutup ekle
int m = int(rhs.pntl.size());
int l = sizl, r = -1;
for (int i = 0; i < m; ++i) {
r = std::max(r, i);
while (true) {
i64 sum = (l == sizl ? 0 : lhs.sumr[l]) + rhs.suml[r];
if (r != m - 1 && sum >= A[rhs.pntl[r] + 1]) {
r++;
continue;
}
if (l != 0 && sum >= A[l == sizl ? lhs.r : (lhs.pntr[l] - 1)]) {
l--;
continue;
}
break;
}
if (r == m - 1) {
res.frqr[l] += rhs.frql[i];
}
}
}
{ // Case 3: sol childimin saga yapisik kaplayanlari buyutup eger saga yapisirlarsa ekle
int m = int(rhs.pntl.size());
int l = sizl, r = -1;
for (int i = sizl - 1; i >= 0; --i) {
l = std::min(l, i);
while (true) {
i64 sum = lhs.sumr[l] + (r == -1 ? 0 : rhs.suml[r]);
if (r != m - 1 && sum >= A[r == -1 ? rhs.l : (rhs.pntl[r] + 1)]) {
r++;
continue;
}
if (l != 0 && sum >= A[lhs.pntr[l] - 1]) {
l--;
continue;
}
break;
}
if (r == m - 1) {
res.frqr[l] += lhs.frqr[i];
}
}
}
}
clear(res.pntl, res.frql, res.suml);
clear(res.pntr, res.frqr, res.sumr);
return res;
}
#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1)
void build(int v, int l, int r) {
if (l == r) {
tree[v] = {l};
return;
}
def;
build(lv, l, mid);
build(rv, mid + 1, r);
tree[v] = tree[lv] + tree[rv];
debug(l, r);
debug(tree[v].l, tree[v].r);
debug(tree[v].pntl);
debug(tree[v].frql);
debug(tree[v].suml);
debug(tree[v].pntr);
debug(tree[v].frqr);
debug(tree[v].sumr);
// if (l == 0 && r == 4) exit(0);
}
void modify(int v, int l, int r, int p, int x) {
if (l == r) {
A[p] = x;
tree[v] = {p};
return;
}
def;
if (p <= mid) {
modify(lv, l, mid, p, x);
} else {
modify(rv, mid + 1, r, p, x);
}
tree[v] = tree[lv] + tree[rv];
}
Info get(int v, int l, int r, int ql, int qr) {
if (ql == l && r == qr) {
return tree[v];
}
def;
if (qr <= mid) {
return get(lv, l, mid, ql, qr);
} else if (mid + 1 <= ql) {
return get(rv, mid + 1, r, ql, qr);
} else {
return get(lv, l, mid, ql, mid)
+ get(rv, mid + 1, r, mid + 1, qr);
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> N;
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
build(0, 0, N - 1);
// exit(0);
int Q;
std::cin >> Q;
for (int _ = 0; _ < Q; ++_) {
int TP;
std::cin >> TP;
if (TP == 1) {
int P, X;
std::cin >> P >> X;
--P;
modify(0, 0, N - 1, P, X);
} else {
int L, R;
std::cin >> L >> R;
--L, --R;
auto nd = get(0, 0, N - 1, L, R);
std::cout << nd.frql.back() << '\n';
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |