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 <iostream>
#pragma GCC optimize("Ofast")
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 1e9 + 7, N = 1e5 + 2;
const ll oo = 1e16;
ll a[N];
int n;
namespace cover {
int t[N * 2];
char tag[N * 2];
int sum(int v, int h) { return tag[v] ? h : t[v]; }
void pull(int p) {
int h = 1;
while(p > 1) {
t[p >> 1] = sum(p, h) + sum(p ^ 1, h);
p >>= 1;
h <<= 1;
}
}
void add(int l, int r, int x) {
if(l == 1 && r == n + 1) return;
l--, r--;
int tl = l, tr = r;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1) tag[l++] += x;
if(r & 1) tag[--r] += x;
}
pull(tl + n), pull(tr - 1 + n);
}
int qry(int l, int r) {
l--, r--;
int res = 0, h = 1;
for(l += n, r += n; l < r; l >>= 1, r >>= 1, h <<= 1) {
if(l & 1) res += sum(l++, h);
if(r & 1) res += sum(--r, h);
}
return res;
}
}
namespace seg {
template<class A, class B> struct DS {
pair<A, B> a[29];
int sz;
DS() { sz = 0; }
void clear() { sz = 0; }
void EB(A& x, B& y) { a[sz++] = {x, y}; }
void PB(pair<A, B>& p) { a[sz++] = p; }
pair<A, B>& operator[](int i) { return a[i]; }
void resize(int s) { sz = s; }
};
struct node {
DS<int, ll> bad_pref, bad_suff;
DS<int, int> bad_seg;
ll sum;
} t[N * 2];
int id(int tl, int tr) {
tl--, tr -= 2;
return (tl + tr) | (tl != tr);
}
void pull(int v, int tl, int tr, int lc, int rc, int posl = INF, int posr = 0) {
for(int i = 0; i < t[lc].bad_pref.sz; i++)
t[v].bad_pref.PB(t[lc].bad_pref[i]);
for(int i = 0; i < t[rc].bad_suff.sz; i++)
t[v].bad_suff.PB(t[rc].bad_suff[i]);
for(int i = 0; i < t[rc].bad_pref.sz; i++) {
ll sum1 = t[rc].bad_pref[i].S + t[lc].sum;
int pos1 = t[rc].bad_pref[i].F;
if(sum1 + a[tl - 1] < a[pos1 + 1])
t[v].bad_pref.EB(pos1, sum1);
}
for(int i = 0; i < t[lc].bad_suff.sz; i++) {
ll sum1 = t[lc].bad_suff[i].S + t[rc].sum;
int pos1 = t[lc].bad_suff[i].F;
if(sum1 + a[tr] < a[pos1 - 1])
t[v].bad_suff.EB(pos1, sum1);
}
int szi = t[lc].bad_suff.sz;
int szj = t[rc].bad_pref.sz;
int i = 0, j = 0;
while(i < szi && t[lc].bad_suff[i].F > posl)
i++;
while(j < szj && t[rc].bad_pref[j].F < posr)
j++;
while(i < szi && j < szj) {
auto& he = t[lc].bad_suff[i], be = t[rc].bad_pref[j];
if(he.S + be.S < min(a[he.F - 1], a[be.F + 1])) {
t[v].bad_seg.EB(he.F, be.F);
cover::add(he.F, be.F + 1, 1);
}
if(a[he.F - 1] < a[be.F + 1])
i++;
else
j++;
}
t[v].sum = t[lc].sum + t[rc].sum;
}
void build(int tl = 1, int tr = n + 1) {
int v = id(tl, tr);
if(tr - tl == 1) {
t[v].sum = a[tl];
if(a[tl] + a[tl - 1] < a[tl + 1])
t[v].bad_pref.EB(tl, a[tl]);
if(a[tl] + a[tl + 1] < a[tl - 1])
t[v].bad_suff.EB(tl, a[tl]);
if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1]) {
t[v].bad_seg.EB(tl, tl);
cover::add(tl, tl + 1, 1);
}
} else {
int tm = (tl + tr + 1) / 2;
build(tl, tm);
build(tm, tr);
pull(v, tl, tr, id(tl, tm), id(tm, tr));
}
}
void upd(int pos, int tl = 1, int tr = n + 1) {
int v = id(tl, tr);
int j = 0;
for(int i = 0; i < t[v].bad_seg.sz; i++) {
auto [l, r] = t[v].bad_seg[i];
if(r < pos - 1 || l > pos + 1) {
t[v].bad_seg[j++] = t[v].bad_seg[i];
} else {
cover::add(l, r + 1, -1);
}
}
t[v].bad_seg.resize(j);
t[v].bad_pref.clear(), t[v].bad_suff.clear();
if(tr - tl == 1) {
t[v].sum = a[tl];
if(a[tl] + a[tl - 1] < a[tl + 1])
t[v].bad_pref.EB(tl, a[tl]);
if(a[tl] + a[tl + 1] < a[tl - 1])
t[v].bad_suff.EB(tl, a[tl]);
if(a[tl] < a[tl + 1] && a[tl] < a[tl - 1]) {
t[v].bad_seg.EB(tl, tl);
cover::add(tl, tl + 1, 1);
}
} else {
int tm = (tl + tr + 1) / 2;
if(pos - 1 < tm)
upd(pos, tl, tm);
if(pos + 1 >= tm)
upd(pos, tm, tr);
pull(v, tl, tr, id(tl, tm), id(tm, tr), pos + 1, pos - 1);
}
}
}
void upd(int pos, ll val) {
a[pos] = val;
seg::upd(pos);
}
#define gc getchar_unlocked
inline int readInt () {
int c = gc();
while(!isdigit(c)) c = gc();
int res = c - '0';
while(isdigit(c = gc())) res = res * 10 + c - '0';
return res;
}
#define pc putchar_unlocked
inline void writeInt (int n) {
int N = n, rev, count = 0;
rev = N;
if (N == 0) { pc('0'); return ;}
while ((rev % 10) == 0) { count++; rev /= 10;}
rev = 0;
while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
while (count--) pc('0');
}
signed main()
{
IO_OP;
n = readInt();
a[0] = a[n + 1] = oo;
for(int i = 1; i <= n; i++)
a[i] = readInt();
seg::build();
int q = readInt();
while(q--) {
int op = readInt();
if(op == 1) {
int x = readInt(), y = readInt();
upd(x, y);
} else {
int l = readInt(), r = readInt();
ll tl = a[l - 1], tr = a[r + 1];
if(l - 1 >= 1) upd(l - 1, 1e15);
if(r + 1 <= n) upd(r + 1, 1e15);
if(l != 1 || r != n)
cover::add(l, r + 1, -1);
writeInt(r - l + 1 - cover::qry(l, r + 1));
pc('\n');
if(l != 1 || r != n)
cover::add(l, r + 1, 1);
if(l - 1 >= 1) upd(l - 1, tl);
if(r + 1 <= n) upd(r + 1, tr);
}
}
}
Compilation message (stderr)
fish2.cpp: In function 'void seg::upd(int, int, int)':
fish2.cpp:142:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
142 | auto [l, r] = t[v].bad_seg[i];
| ^
# | 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... |