Let's create a merge sort tree where each node has a sorted vector containing all elements in the range of this node. Now we can answer the query recursively like a segment tree. For some $$$node$$$ if $$$[l_{node},r_{node}]$$$ is outside $$$[l_i,r_i]$$$ its answer is obviously $$$0$$$. If its entirely contained, we can do binary search on the vector to find how many elements satisfy the conditions. If neither of the previous conditions are satisfied, we take the answer of the right child + the answer of the left child. Time complexity for building the merge sort tree is $$$O(nlogn)$$$ because we go through each element $$$logn$$$ times, and the time complexity for answering the queries is $$$O(qlog^2n)$$$ because in each query we visit logn nodes at most, doing binary search in each one in $$$O(logn)$$$.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,a[N];
vector<int> seg[4*N+5];
//build merge sort tree
void build(int node,int l,int r){
    //if range length is 1 there's only one element to add and no children
    if (l==r){
        seg[node].push_back(a[l]);
        return;
    }int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    int i=0,j=0;
    // use two pointers to merge the two vectors in O(r-l+1)
    while (i<seg[node*2].size() && j<seg[node*2+1].size()){
        if (seg[node*2][i]<seg[node*2+1][j]) seg[node].push_back(seg[node*2][i++]);
        else seg[node].push_back(seg[node*2+1][j++]);
    }
    while (i<seg[node*2].size()) seg[node].push_back(seg[node*2][i++]);
    while (j<seg[node*2+1].size()) seg[node].push_back(seg[node*2+1][j++]);
    return;
}
//query
int query(int node,int l,int r,int lx,int rx,int x){
    //if outside -> 0
    if (l>rx || r<lx) return 0;
    //if inside do binary search
    if (l>=lx && r<=rx){
        int L=0,R=seg[node].size()-1,mid,ans=0;
        while (L<=R){
            mid=(L+R)/2;
            if (seg[node][mid]<x){
                ans=mid+1;
                L=mid+1;
            }else R=mid-1;
        }return ans;
    }
    int mid=(l+r)/2;
    return query(node*2,l,mid,lx,rx,x)+query(node*2+1,mid+1,r,lx,rx,x);
}
int32 main(){
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while (q--){
        int l,r,x;
        cin>>l>>r>>x;
        cout<<query(1,1,n,l,r,x)<<endl;
    }
    return 0;
}

Let's create something similar to merge sort tree, where each node has a multiset of the elements in its range, we can loop through these values. Building time complexity is $$$O(nlog^2 n)$$$ because we add each element $$$logn$$$ times with time complexity $$$O(logn)$$$ because multiset. Now to the queries. When we are supposed to change some element, we go through the segment tree and remove it from each node that contains it and add its new value instead. This is also in $$$O(log^2 n )$$$ because we add to $$$logn$$$ nodes at most, each with time complexity $$$O(logn)$$$ because multiset. Now for the other type of queries, we do similar to the previous problem. If a node is outside the query range we return $$$INF$$$. If a node is entirely inside the query range we return the lower bound in this node's multiset. Else we want the minimum of the answer of the node's right child and left child answers. Time complexity of this queries is $$$O(log^2n)$$$ because we go through $$$logn$$$ nodes at worst case each with time complexity $$$O(logn)$$$ because of binary search (lower bound function). Time compleixty overall: $$$O((q+n)log^2n)$$$.

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,a[N];
multiset<int> seg[4*N+5];
void build(int node,int l,int r){
    if (l==r){
        seg[node].insert(a[l]);
        return;
    }int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    for (int i=l;i<=r;i++) seg[node].insert(a[i]);
    return;
}
void edit(int node,int l,int r,int idx,int val){
    if (l==r){
        seg[node].erase(a[idx]);
        seg[node].insert(val);
        return;
    }int mid=(l+r)/2;
    if (idx<=mid) edit(node*2,l,mid,idx,val);
    else edit(node*2+1,mid+1,r,idx,val);
    seg[node].erase(a[idx]);
    seg[node].insert(val);
    return;
}
int query(int node,int l,int r,int lx,int rx,int x){
    if (l>rx || r<lx) return INT_MAX;
    if (l>=lx && r<=rx){
        auto it=seg[node].lower_bound(x);
        if (it==seg[node].end()) return INT_MAX;
        return *it;
    }int mid=(l+r)/2;
    return min(query(node*2,l,mid,lx,rx,x),query(node*2+1,mid+1,r,lx,rx,x));
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while (q--){
        bool t;cin>>t;
        if (!t){
            int idx,val;
            cin>>idx>>val;
            edit(1,1,n,idx,val);
            a[idx]=val;
            continue;
        }int l,r,x;cin>>l>>r>>x;
        int y=query(1,1,n,l,r,x);
        if (y==INT_MAX) cout<<-1<<endl;
        else cout<<y<<endl;
    }
    return 0;
}