KQuery 2

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const double eps = 1e-9;
const double PI = atan(1.0);
#define readFile freopen("input","r",stdin);
#define writeFile freopen("output","w",stdout);
#define fastIO ios::sync_with_stdio(0);
typedef pair<int ,int> ii;
typedef unsigned long long ULL;
const int N=30001;
struct Node{
    int freq,sz,height,val;
    Node*l,*r;
    Node(){
        l=r=NULL;
        freq = sz = height = val = 0;
    }
    Node(int val){
        freq = sz = height = 1;
        this->val = val;
    }
    void fix(){
        int lh = l?l->height:0;
        int rh = r?r->height:0;
        int ls = l?l->sz:0;
        int rs = r?r->sz:0;
        height = max(lh,rh)+1;
        sz = ls+rs+freq;
    }
    int fb(){
        int lh = l?l->height:0;
        int rh = r?r->height:0;
        return lh-rh;
    }
};

void lrotate(Node* &node){
    Node* temp = node->r;
    node->r = temp->l;
    temp->l = node;
    node->fix();
    node = temp;
    node->fix();
}

void rrotate(Node* &node){
    Node* temp = node->l;
    node->l = temp->r;
    temp->r = node;
    node->fix();
    node = temp;
    node->fix();
}

void rotate(Node* &node){
    if (node->fb()>1){
        if (node->l->fb()<0)
            lrotate(node->l);
        rrotate(node);
    }
    else if (node->fb()<-1){
        if (node->r->fb()>0)
            rrotate(node->r);
        lrotate(node);
    }
}

Node* getMin(Node* node){
    if (!node->l) return node;
    return getMin(node->l);
}

void insert(Node* &node,int val){
    if (!node){
        node = new Node(val);
        return;
    }
    if (node->val==val){
        node->freq++;
    }
    else if (node->val>val){
        insert(node->l,val);
    }
    else{
        insert(node->r,val);
    }
    node->fix();
    rotate(node);
}

void remove(Node* &node,int val){
    if (!node) return;
    if (node->val > val) remove(node->l,val);
    else if (node->val < val) remove(node->r,val);
    else{
        if (node->freq>1) node->freq--;
        else{
            if (!node->r || !node-> l){
                Node* temp = node->l?node->l:node->r;
                node = temp;
                return;
            }
            else{
                Node* temp = getMin(node->r);
                int t = temp->freq;
                temp->freq = 1;
                remove(node->r,temp->val);
                temp->freq = t;
                temp->l = node->l;
                temp->r = node->r;
                node = temp;
            }
        }
    }
    node->fix();
    rotate(node);
}

int query(Node* node,int val){
    if (!node) return 0;
    if (node->val > val) return query(node->l,val);
    if (node->val < val) return node->freq + (node->l?node->l->sz:0)+query(node->r,val);
    return node->freq + (node->l?node->l->sz:0);
}

Node* tree[N*4];
int n,q;
int arr[N];

void sInsert(int node,int l,int r,int idx,int val){
    insert(tree[node],val);
    if (l==r) return;
    int mid = (l+r)>>1;
    if (idx<=mid) sInsert(node<<1,l,mid,idx,val);
    else sInsert(node<<1|1,mid+1,r,idx,val);
}

void sRemove(int node,int l,int r,int idx,int val,int val2){
    remove(tree[node],val);
    insert(tree[node],val2);
    if (l==r){
        arr[l]=val2;
        return;
    }
    int mid = (l+r)>>1;
    if (idx<=mid) sRemove(node<<1,l,mid,idx,val,val2);
    else sRemove(node<<1|1,mid+1,r,idx,val,val2);
}

int sQuery(int node,int l,int r,int ll,int rr,int val){
    if (l>rr || r<ll) return 0;
    if (l>=ll && r<=rr) return query(tree[node],val);
    int mid = (l+r)>>1;
    return sQuery(node<<1,l,mid,ll,rr,val)+sQuery(node<<1|1,mid+1,r,ll,rr,val);
}
int main(){
#ifndef ONLINE_JUDGE
    readFile;
//    writeFile;
#endif
    fastIO;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        sInsert(1,1,n,i,arr[i]);
    }
    scanf("%d",&q);
    while (q--){
        int t; scanf("%d",&t);
        if (t){
            int i,j,k; scanf("%d%d%d",&i,&j,&k);
            printf("%d\n",j-i+1-sQuery(1,1,n,i,j,k));
        }
        else{
            int i,v; scanf("%d%d",&i,&v);
            sRemove(1,1,n,i,arr[i],v);
        }
    }
}