//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
//#define int long long
#define in insert
#define mid (l+r)/2
#define in insert
using namespace std;
const int N=1e5+6;
int tree[N*40],b[N],n,m;
void upd(int node , int l , int r , int s,int e, int v){
//cout<<" # "<<node<<' '<<l<<' '<<r<<endl;
if(l>=s && r<=e){
tree[node]+=v;
return ;
}
else if(l>e || r<s) return ;
upd(node*2,l,mid,s,e,v);
upd(node*2+1,mid+1,r,s,e,v);
return ;
}
int query(int node , int l , int r , int id){
if(l>id || r<id) return 0;
else if(l==r) return tree[node];
return tree[node]+query(node*2,l,mid,id)+query(node*2+1,mid+1,r,id);
}
void modify(int id , int val){
if(id+1<=n){
upd(1,1,1e6,min(b[id],b[id+1]),max(b[id],b[id+1]),-1);
upd(1,1,1e6,min(val,b[id+1]),max(val,b[id+1]),1);
}
if(id-1>=1){
upd(1,1,1e6,min(b[id],b[id-1]),max(b[id],b[id-1]),-1);
upd(1,1,1e6,min(val,b[id-1]),max(val,b[id-1]),1);
}
return ;
}
int32_t main(){
ios::sync_with_stdio(false);cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=1;i<n;i++){
int l=min(b[i],b[i+1]),r=max(b[i],b[i+1]);
upd(1,1,1e6,l,r,1);
}
for(int i=1;i<=m;i++){
int op;cin>>op;
if(op==1){
int pos,val;
cin>>pos>>val;
modify(pos,val);
}
else{
int id;cin>>id;
cout<<query(1,1,1e6,id)<<endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
