Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
For a fixed left endpoint , look at . This value never increases as grows, while strictly increases. So a segment can have at most one nasty number. That cuts the problem down a lot.
The only question for query is whether the unique crossing exists before . Define Then is strictly decreasing by at least each step, because the minimum cannot increase. We need to know whether for some .
Since all , is never valid. Also if , then the crossing has not happened yet. So existence is controlled by where first becomes non-positive.
For each position , define as the smallest such that Then query returns exactly when and the minimum at that prefix is exactly . Because drops in integer steps, the first non-positive point can be equality or it can skip below zero.
Compute that first non-positive point with binary search. A segment tree gives under point updates in , so each type- query costs and each update costs . The answer is never more than ; the binary search only decides whether that one exists.
For a fixed query , define for .
A number is nasty exactly when .
The important observation is brutally simple: is non-increasing as grows, while itself is increasing. So two different nasty values cannot exist. If and , then so is impossible.
Therefore every type- query answers only or . We just need to decide whether the unique possible equality happens inside the segment.
Now define Since never increases, when increases by , decreases by at least : So is strictly decreasing. Also , hence meaning is never nasty. No sneaky zero case, thank god.
Because is strictly decreasing, we can binary search for the first index where which is the same as Call this index .
There are three cases:
That last case matters. Binary search finds the first non-positive point, not automatically a solution. Assuming the crossing always lands exactly on zero is how bugs get fed.
To support updates, keep a segment tree over the array storing minimums. Then:
The constraints allow this easily: across all test cases, with memory.
Edge cases:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct SegTree {
int n;
vector<int> st;
SegTree() : n(0) {}
SegTree(const vector<int>& a) { init(a); }
void init(const vector<int>& a) {
n = (int)a.size() - 1;
st.assign(4 * n + 4, INT_MAX);
build(1, 1, n, a);
}
void build(int p, int l, int r, const vector<int>& a) {
if (l == r) {
st[p] = a[l];
return;
}
int m = (l + r) / 2;
build(p * 2, l, m, a);
build(p * 2 + 1, m + 1, r, a);
st[p] = min(st[p * 2], st[p * 2 + 1]);
}
void update(int idx, int val) { update(1, 1, n, idx, val); }
void update(int p, int l, int r, int idx, int val) {
if (l == r) {
st[p] = val;
return;
}
int m = (l + r) / 2;
if (idx <= m) update(p * 2, l, m, idx, val);
else update(p * 2 + 1, m + 1, r, idx, val);
st[p] = min(st[p * 2], st[p * 2 + 1]);
}
int query(int ql, int qr) { return query(1, 1, n, ql, qr); }
int query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return st[p];
int m = (l + r) / 2;
int ans = INT_MAX;
if (ql <= m) ans = min(ans, query(p * 2, l, m, ql, qr));
if (qr > m) ans = min(ans, query(p * 2 + 1, m + 1, r, ql, qr));
return ans;
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
SegTree seg(a);
while (q--) {
int type;
cin >> type;
if (type == 1) {
int i, x;
cin >> i >> x;
seg.update(i, x);
} else {
int l, r;
cin >> l >> r;
int len = r - l;
int lo = 0, hi = len, pos = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int mn = seg.query(l, l + mid);
if (mn <= mid) {
pos = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
int ans = 0;
if (pos != -1 && seg.query(l, l + pos) == pos) ans = 1;
cout << ans << '\n';
}
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct SegTree {
int n;
vector<int> st;
SegTree() : n(0) {}
SegTree(const vector<int>& a) { init(a); }
void init(const vector<int>& a) {
n = (int)a.size() - 1;
st.assign(4 * n + 4, INT_MAX);
build(1, 1, n, a);
}
void build(int p, int l, int r, const vector<int>& a) {
if (l == r) {
st[p] = a[l];
return;
}
int m = (l + r) / 2;
build(p * 2, l, m, a);
build(p * 2 + 1, m + 1, r, a);
st[p] = min(st[p * 2], st[p * 2 + 1]);
}
void update(int idx, int val) { update(1, 1, n, idx, val); }
void update(int p, int l, int r, int idx, int val) {
if (l == r) {
st[p] = val;
return;
}
int m = (l + r) / 2;
if (idx <= m) update(p * 2, l, m, idx, val);
else update(p * 2 + 1, m + 1, r, idx, val);
st[p] = min(st[p * 2], st[p * 2 + 1]);
}
int query(int ql, int qr) { return query(1, 1, n, ql, qr); }
int query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return st[p];
int m = (l + r) / 2;
int ans = INT_MAX;
if (ql <= m) ans = min(ans, query(p * 2, l, m, ql, qr));
if (qr > m) ans = min(ans, query(p * 2 + 1, m + 1, r, ql, qr));
return ans;
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
SegTree seg(a);
while (q--) {
int type;
cin >> type;
if (type == 1) {
int i, x;
cin >> i >> x;
seg.update(i, x);
} else {
int l, r;
cin >> l >> r;
int len = r - l;
int lo = 0, hi = len, pos = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int mn = seg.query(l, l + mid);
if (mn <= mid) {
pos = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
int ans = 0;
if (pos != -1 && seg.query(l, l + pos) == pos) ans = 1;
cout << ans << '\n';
}
}
}
return 0;
}