#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=0; 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=0; 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());
seg.update(0, A[0], 1, 0, v.size(), 1);
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[max(0, Q[i].a-2)], A[min((int)N-1, Q[i].a)]);
h = max(A[max(0, Q[i].a-2)], A[min((int)N-1, Q[i].a)]);
if (A[Q[i].a] < Q[i].b) {
seg.update(A[Q[i].a-1]+1, l, -1, 0, v.size(), 1);
seg.update(h+1, Q[i].b, 1, 0, v.size(), 1);
A[Q[i].a-1] = Q[i].b;
}
else {
seg.update(Q[i].b+1, l, 1, 0, v.size(), 1);
seg.update(h+1, A[Q[i].a-1], -1, 0, v.size(), 1);
A[Q[i].a-1] = 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 |
4 ms |
564 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 |
28 ms |
2936 KB |
Output is correct |
| 5 |
Correct |
54 ms |
5368 KB |
Output is correct |
| 6 |
Correct |
85 ms |
8060 KB |
Output is correct |
| 7 |
Correct |
140 ms |
11988 KB |
Output is correct |
| 8 |
Correct |
188 ms |
14932 KB |
Output is correct |
| 9 |
Correct |
344 ms |
24380 KB |
Output is correct |
| 10 |
Correct |
325 ms |
22560 KB |
Output is correct |
| 11 |
Correct |
408 ms |
27852 KB |
Output is correct |
| 12 |
Correct |
549 ms |
30960 KB |
Output is correct |
| 13 |
Correct |
446 ms |
31108 KB |
Output is correct |
| 14 |
Correct |
412 ms |
30496 KB |
Output is correct |
| 15 |
Correct |
430 ms |
30696 KB |
Output is correct |
| 16 |
Correct |
423 ms |
31560 KB |
Output is correct |
| 17 |
Correct |
426 ms |
31592 KB |
Output is correct |
| 18 |
Correct |
425 ms |
31480 KB |
Output is correct |
| 19 |
Correct |
430 ms |
31592 KB |
Output is correct |
| 20 |
Correct |
423 ms |
31344 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 |
4 ms |
564 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
