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>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
struct Query{
int t, a, b;
} Q[202020];
int N, M;
int A[202020];
vector<int> v;
struct SEG {
vector<ll> tree, lazy;
void init(int n) {
tree.resize(4*n), lazy.resize(4*n);
}
void lpush(int lo, int hi, int idx) {
if (lazy[idx] == 0) return;
tree[idx] += (hi-lo+1)*lazy[idx];
if (lo==hi) { lazy[idx] = 0; return; }
lazy[2*idx] += lazy[idx];
lazy[2*idx+1] += lazy[idx];
lazy[idx] = 0; return;
}
ll update(int a, int b, int x, int lo, int hi, int idx) {
lpush(lo, hi, idx);
if (b<lo || a>hi) return tree[idx];
if (a<=lo && hi<=b) {
lazy[idx] += x; lpush(lo, hi, idx);
return tree[idx];
}
return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
}
ll query(int a, int b, int lo, int hi, int idx) {
lpush(lo, hi, idx);
if (b<lo || a>hi) return 0;
if (a<=lo && hi<=b) return tree[idx];
return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
}
} seg;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> N >> M;
for (int i=1; i<=N; i++) { cin >> A[i]; v.push_back(A[i]); }
for (int i=0; i<M; i++) {
cin >> Q[i].t;
if (Q[i].t == 1) { cin >> Q[i].a; v.push_back(Q[i].a); }
else { cin >> Q[i].a >> Q[i].b; v.push_back(Q[i].b); }
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i=1; i<=N; i++)
A[i] = lower_bound(v.begin(), v.end(), A[i])-v.begin();
for (int i=0; i<M; i++) {
if (Q[i].t==1) Q[i].a = lower_bound(v.begin(), v.end(), Q[i].a)-v.begin();
else Q[i].b = lower_bound(v.begin(), v.end(), Q[i].b)-v.begin();
}
seg.init(v.size());
A[0] = -1; A[N+1] = 2e9;
for (int i=1; i<=N; i++) {
if (A[i-1] < A[i]) seg.update(A[i-1]+1, A[i], 1, 0, v.size(), 1);
}
for (int i=0; i<M; i++) {
if (Q[i].t == 1) cout << seg.query(Q[i].a, Q[i].a, 0, v.size(), 1) << '\n';
else {
int l, h;
l = min(A[Q[i].a-1], A[Q[i].a+1]);
h = max(A[Q[i].a-1], A[Q[i].a+1]);
if (A[Q[i].a] < Q[i].b) {
seg.update(A[Q[i].a]+1, min(l, Q[i].b), -1, 0, v.size(), 1);
seg.update(max(h, A[Q[i].a])+1, Q[i].b, 1, 0, v.size(), 1);
A[Q[i].a] = Q[i].b;
}
else {
seg.update(Q[i].b+1, min(l, A[Q[i].a]), 1, 0, v.size(), 1);
seg.update(max(h, Q[i].b)+1, A[Q[i].a], -1, 0, v.size(), 1);
A[Q[i].a] = Q[i].b;
}
}
}
}
Compilation message (stderr)
employment.cpp: In member function 'll SEG::update(int, int, int, int, int, int)':
employment.cpp:40:44: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
~~^~~
employment.cpp:40:82: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return tree[idx] = update(a, b, x, lo, lo+hi>>1, 2*idx) + update(a, b, x, 1+(lo+hi>>1), hi, 2*idx+1);
~~^~~
employment.cpp: In member function 'll SEG::query(int, int, int, int, int)':
employment.cpp:48:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
~~^~~
employment.cpp:48:62: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return query(a, b, lo, lo+hi>>1, 2*idx) + query(a, b, 1+(lo+hi>>1), hi, 2*idx+1);
~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |