#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 5, M = (1<<20);
int T[N];
int sh[N];
void update (int k, int l, int r, int L, int R, int x){
if (r < L || R < l)
return;
if (L <= l && r <= R){
T[k] += (r - l + 1) * x;
sh[k] += x;
return;
}
update (k * 2, l, (l + r) / 2, L, R, x + sh[k]);
update (k * 2 + 1, (l + r) / 2 + 1, r, L, R, x + sh[k]);
sh[k] = 0;
T[k] = T[k * 2] + T[k * 2 + 1];
}
int calc (int k, int l, int r, int x){
if (r < x || x < l)
return 0;
if (l == r)
return T[k];
update (k * 2, l, (l + r) / 2, l, (l + r) / 2, sh[k]);
update (k * 2 + 1, (l + r) / 2 + 1, r, (l + r) / 2 + 1, r, sh[k]);
sh[k] = 0;
T[k] = T[k * 2] + T[k * 2 + 1];
return calc (k * 2, l, (l + r) / 2, x) +
calc (k * 2 + 1, (l + r) / 2 + 1, r, x);
}
int n, m;
int a[N];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for (int i = 1; i <= n; i++)
cin>>a[i];
for (int i = 1; i < n; i++){
int x = min (a[i], a[i + 1]);
int y = max (a[i], a[i + 1]);
update (1, 1, M, x, y, 1);
}
while (m--){
int t;
cin>>t;
if (t == 1){
int l, x;
cin>>l>>x;
if (l > 1){
update (1, 1, M, min (a[l], a[l - 1]), max (a[l], a[l - 1]), -1);
update (1, 1, M, min (x, a[l - 1]), max (x, a[l - 1]), 1);
}
if (l < n){
update (1, 1, M, min (a[l], a[l + 1]), max (a[l], a[l + 1]), -1);
update (1, 1, M, min (x, a[l + 1]), max (x, a[l + 1]), 1);
}
a[l] = x;
continue;
}
int x;
cin>>x;
cout<<calc (1, 1, M, x)<<endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
14508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
14508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
18 ms |
14508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
