#include<bits/stdc++.h>
using namespace std;
const int VMAX = 1e6+ 5;
const int N = 1e5 + 5;
int aib[VMAX];
void upd_aib(int poz,int val){
for(int i = poz; i < VMAX; i+= i&(-i))
aib[i] += val;
}
int query(int poz){
int ans = 0;
for(int i = poz; i>0; i-= i&(-i)){
ans += aib[i];
}
return ans;
}
void update(int a, int b, int val){
if( a > b)
swap(a, b);
upd_aib(a, val);
upd_aib(b + 1, - val);
}
int v[N];
int main()
{
//freopen(".in","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n, q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>v[i];
}
for(int i = 2; i<=n;i++){
update(v[i-1], v[i], 1);
}
for(int i=1; i<=q;i++){
int tip;
cin>>tip;
if(tip == 1){
int p, val;
cin>>p>>val;
if(p > 1)
update(v[p-1], v[p], -1);
if(p < n)
update(v[p], v[p + 1], -1);
v[p] = val;
if(p > 1)
update(v[p-1], v[p], 1);
if(p < n)
update(v[p], v[p + 1], 1);
}
else{
int h;
cin>>h;
cout<<query(h)<<"\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
4204 KB |
Output is correct |
3 |
Correct |
3 ms |
4204 KB |
Output is correct |
4 |
Correct |
3 ms |
4204 KB |
Output is correct |
5 |
Correct |
3 ms |
4204 KB |
Output is correct |
6 |
Correct |
3 ms |
4204 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
4204 KB |
Output is correct |
3 |
Correct |
3 ms |
4204 KB |
Output is correct |
4 |
Correct |
3 ms |
4204 KB |
Output is correct |
5 |
Correct |
3 ms |
4204 KB |
Output is correct |
6 |
Correct |
3 ms |
4204 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
39 ms |
1772 KB |
Output is correct |
9 |
Correct |
54 ms |
6892 KB |
Output is correct |
10 |
Correct |
51 ms |
6892 KB |
Output is correct |
11 |
Correct |
42 ms |
1644 KB |
Output is correct |
12 |
Correct |
44 ms |
2924 KB |
Output is correct |
13 |
Correct |
43 ms |
2796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
3 ms |
4204 KB |
Output is correct |
3 |
Correct |
3 ms |
4204 KB |
Output is correct |
4 |
Correct |
3 ms |
4204 KB |
Output is correct |
5 |
Correct |
3 ms |
4204 KB |
Output is correct |
6 |
Correct |
3 ms |
4204 KB |
Output is correct |
7 |
Correct |
2 ms |
364 KB |
Output is correct |
8 |
Correct |
39 ms |
1772 KB |
Output is correct |
9 |
Correct |
54 ms |
6892 KB |
Output is correct |
10 |
Correct |
51 ms |
6892 KB |
Output is correct |
11 |
Correct |
42 ms |
1644 KB |
Output is correct |
12 |
Correct |
44 ms |
2924 KB |
Output is correct |
13 |
Correct |
43 ms |
2796 KB |
Output is correct |
14 |
Correct |
64 ms |
6892 KB |
Output is correct |
15 |
Correct |
66 ms |
6892 KB |
Output is correct |
16 |
Correct |
68 ms |
6892 KB |
Output is correct |
17 |
Correct |
65 ms |
6892 KB |
Output is correct |
18 |
Correct |
72 ms |
6892 KB |
Output is correct |