#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
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 |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
5 ms |
760 KB |
Output is correct |
| 3 |
Correct |
5 ms |
760 KB |
Output is correct |
| 4 |
Correct |
27 ms |
3064 KB |
Output is correct |
| 5 |
Correct |
54 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
85 ms |
8052 KB |
Output is correct |
| 7 |
Correct |
148 ms |
12068 KB |
Output is correct |
| 8 |
Correct |
197 ms |
14996 KB |
Output is correct |
| 9 |
Correct |
351 ms |
24472 KB |
Output is correct |
| 10 |
Correct |
323 ms |
22376 KB |
Output is correct |
| 11 |
Correct |
374 ms |
27888 KB |
Output is correct |
| 12 |
Correct |
423 ms |
30912 KB |
Output is correct |
| 13 |
Correct |
467 ms |
31148 KB |
Output is correct |
| 14 |
Correct |
417 ms |
30524 KB |
Output is correct |
| 15 |
Correct |
446 ms |
30708 KB |
Output is correct |
| 16 |
Correct |
438 ms |
31548 KB |
Output is correct |
| 17 |
Correct |
431 ms |
31596 KB |
Output is correct |
| 18 |
Correct |
428 ms |
31344 KB |
Output is correct |
| 19 |
Correct |
432 ms |
31464 KB |
Output is correct |
| 20 |
Correct |
429 ms |
31464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
