/**
* author: wxhtzdy
* created: 07.08.2023 10:57:57
**/
#include <bits/stdc++.h>
using namespace std;
namespace mncnt {
struct node {
int mn;
int cnt;
};
node comb(node l, node r) {
node res;
res.mn = min(l.mn, r.mn);
res.cnt = (l.mn == res.mn ? l.cnt : 0) + (r.mn == res.mn ? r.cnt : 0);
return res;
}
vector<node> st;
vector<int> lzy;
int n;
void init(int _n) {
n = _n;
st.resize(8 * n);
lzy.resize(8 * n);
}
void push(int x) {
st[2 * x].mn += lzy[x];
st[2 * x + 1].mn += lzy[x];
lzy[2 * x] += lzy[x];
lzy[2 * x + 1] += lzy[x];
lzy[x] = 0;
}
void pull(int x) {
st[x] = comb(st[2 * x], st[2 * x + 1]);
}
void build(int x, int l, int r) {
if (l == r) {
st[x].mn = 0;
st[x].cnt = 1;
return;
}
int mid = l + r >> 1;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
pull(x);
}
void update(int x, int l, int r, int ll, int rr, int v) {
if (l > r || l > rr || r < ll || ll > rr) {
return;
}
if (ll <= l && r <= rr) {
lzy[x] += v;
st[x].mn += v;
push(x);
return;
}
push(x);
int mid = l + r >> 1;
update(x * 2, l, mid, ll, rr, v);
update(x * 2 + 1, mid + 1, r, ll, rr, v);
pull(x);
}
node query(int x, int l, int r, int ll, int rr) {
if (l > r || l > rr || r < ll || ll > rr) {
return {(int) 1e9, 0};
}
if (ll <= l && r <= rr) {
return st[x];
}
int mid = l + r >> 1;
return comb(query(2 * x, l, mid, ll, rr), query(2 * x + 1, mid + 1, r, ll, rr));
}
void update(int l, int r, int v) {
update(1, 0, n - 1, l, r, v);
}
int get(int l, int r) {
if (l > r) {
return 0;
}
node nd = query(1, 0, n - 1, l, r);
return nd.mn == 0 ? nd.cnt : 0;
}
};
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
fenwick<long long> fenw(n);
for (int i = 0; i < n; i++) {
fenw.modify(i, a[i]);
}
auto GetSum = [&](int L, int R) {
return fenw.get(R) - fenw.get(L - 1);
};
const int inf = (int) 1e9;
auto Valid = [&](int L, int R) {
if (L + 1 >= R) {
return false;
}
return min((L < 0 ? inf : a[L]), (R >= n ? inf : a[R])) > GetSum(L + 1, R - 1);
};
vector<vector<pair<int, int>>> segs(8 * n);
function<void(int, int, int, int, int, int, int)> Add = [&](int x, int l, int r, int ll, int rr, int vl, int vr) {
if (l > r || l > rr || r < ll || ll > rr) {
return;
}
if (ll <= l && r <= rr) {
segs[x].emplace_back(vl, vr);
return;
}
int mid = l + r >> 1;
Add(x * 2, l, mid, ll, rr, vl, vr);
Add(x * 2 + 1, mid + 1, r, ll, rr, vl, vr);
};
mncnt::init(n);
auto Build = [&]() {
mncnt::build(1, 0, n - 1);
vector<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.back()] < a[i]) {
if (Valid(stk.back(), i)) {
Add(1, 0, n - 1, max(0, stk.back()), i, stk.back() + 1, i - 1);
mncnt::update(stk.back() + 1, i - 1, 1);
}
stk.pop_back();
}
if (stk.empty()) {
if (Valid(-1, i)) {
Add(1, 0, n - 1, 0, i, 0, i - 1);
mncnt::update(0, i - 1, 1);
}
}
stk.push_back(i);
}
stk.clear();
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty() && a[stk.back()] < a[i]) {
if (Valid(i, stk.back())) {
Add(1, 0, n - 1, i, min(n - 1, stk.back()), i + 1, stk.back() - 1);
mncnt::update(i + 1, stk.back() - 1, 1);
}
stk.pop_back();
}
if (stk.empty()) {
if (Valid(i, n)) {
Add(1, 0, n - 1, i, n - 1, i + 1, n - 1);
mncnt::update(i + 1, n - 1, 1);
}
}
stk.push_back(i);
}
};
int q;
cin >> q;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int x, y;
cin >> x >> y;
--x;
fenw.modify(x, y - a[x]);
a[x] = y;
} else {
Build();
int l, r;
cin >> l >> r;
--l; --r;
{
int L = l;
for (int i = l + 1; i <= r; i++) {
if (GetSum(L, i - 1) < a[i]) {
l = i;
}
}
}
{
int R = r;
for (int i = r - 1; i >= l; i--) {
if (GetSum(i + 1, R) < a[i]) {
r = i;
}
}
}
cout << mncnt::get(l, r) << '\n';
}
}
return 0;
}
Compilation message
fish2.cpp: In function 'void mncnt::build(int, int, int)':
fish2.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int mid = l + r >> 1;
| ~~^~~
fish2.cpp: In function 'void mncnt::update(int, int, int, int, int, int)':
fish2.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid = l + r >> 1;
| ~~^~~
fish2.cpp: In function 'mncnt::node mncnt::query(int, int, int, int, int)':
fish2.cpp:72:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid = l + r >> 1;
| ~~^~~
fish2.cpp: In lambda function:
fish2.cpp:143:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
143 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
