Salary Queries

1#include<bits/stdc++.h>
2using namespace std;
3struct node{
4  int l,r,m,v;
5  node *lf,*rg;
6  node(int _l,int _r):l(_l),r(_r),m((_l+_r)>>1),v(0) {
7    lf=nullptr,
8    rg=nullptr;
9  }
10  void upd(int x,int d){
11    if(l==r){
12      v+=d;
13      return;
14    }
15    if(x<=m){ if(!lf) lf=new node(l,m);
16    }else if(!rg) rg=new node(m+1,r);
17    (x<=m?lf:rg)->upd(x,d);
18    v=(lf?lf->v:0)+(rg?rg->v:0);
19  }
20  int qry(int a,int b){
21    if(a<=l && r<=b) return v;
22    if(a>r || b<l) return 0;
23    return (lf?lf->qry(a,b):0)+(rg?rg->qry(a,b):0);
24  }
25}*root;
26signed main(){
27  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
28  int n,q; cin>>n>>q;
29  int p[n]; for(int i=0;i<n;++i){
30    cin>>p[i];
31  }
32  root=new node(1,1e9);
33  for(int i=0;i<n;++i) root->upd(p[i],1);
34  while(q--){
35    char c; int a,b;
36    cin>>c>>a>>b;
37    if(c=='?') cout<<root->qry(a,b)<<'\n';
38    else{
39      root->upd(p[--a],-1);
40      p[a]=b;
41      root->upd(p[a],1);
42    }
43  }
44  return 0;
45}