This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
const int MXN = 100005;
int n, m, t, x, y;
ll a[MXN];
int L[MXN], R[MXN], hl[MXN], hr[MXN];
struct BIT {
ll p[MXN];
void init(int n, ll *a) {
p[0] = 0;
FOR(i, 1, n + 1) p[i] = p[i - 1] + a[i];
}
ll query(int l, int r) {
return p[r] - p[l - 1];
}
} B;
void MODIFY(int p, int v) {
a[p] = v;
B.init(n, a);
}
void BUILD(int l, int r) {
vector<pii> st;
{
st.push_back(mp(INT_MAX, -1));
FOR(i, l, r) {
L[i] = -1;
while (st.back().fs <= a[i]) {
L[i] = st.back().sc;
st.pop_back();
}
st.push_back(mp(a[i], i));
}
st.clear();
}
{
st.push_back(mp(INT_MAX, -1));
for (int i = r - 1; i >= l; i--) {
R[i] = -1;
while (st.back().fs < a[i]) {
R[i] = st.back().sc;
st.pop_back();
}
st.push_back(mp(a[i], i));
}
st.clear();
}
{
st.push_back(mp(INT_MAX, l - 1));
FOR(i, l, r) {
while (st.back().fs <= a[i]) st.pop_back();
hl[i] = st.back().sc;
st.push_back(mp(a[i], i));
}
st.clear();
}
{
st.push_back(mp(INT_MAX, r));
for (int i = r - 1; i >= l; i--) {
while (st.back().fs < a[i]) st.pop_back();
hr[i] = st.back().sc;
st.push_back(mp(a[i], i));
}
st.clear();
}
}
void DFS(int id, int bnd, int &ans) {
if (id == -1) return;
debug(id);
if (B.query(hl[id] + 1, hr[id] - 1) < bnd) return;
ans++;
DFS(L[id], a[id], ans);
DFS(R[id], a[id], ans);
}
int MAX_ID(int l, int r) {
int id = l;
FOR(i, l + 1, r) if (a[i] >= a[id]) id = i;
return id;
}
int QUERY(int l, int r) {
BUILD(l, r);
int rt = MAX_ID(l, r);
int ans = 0;
DFS(rt, 0, ans);
return ans;
}
void miku() {
cin >> n;
FOR(i, 1, n + 1) cin >> a[i];
B.init(n, a);
cin >> m;
while (m--) {
cin >> t >> x >> y;
if (t == 1) MODIFY(x, y);
else cout << QUERY(x, y + 1) << '\n';
}
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message (stderr)
fish2.cpp: In function 'void DFS(int, int, int&)':
fish2.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
fish2.cpp:90:5: note: in expansion of macro 'debug'
90 | debug(id);
| ^~~~~
# | 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... |