По условию задачи, есть 2 вида запросов:

1) Вывести количество элементов на отрезке $$$[l,r]$$$, то есть от позиции $$$l$$$ до позиции $$$r$$$ количество таких $$$a_i$$$, что $$$a_i$$$ $$$\ge$$$ $$$c$$$.

2) Поменять значение на позиции $$$pos$$$ на $$$val$$$.

Как будем хранить элементы массива?

Используем метод Sqrt-декомпозиции. Это такой метод (структура данных), которая позволяет нам работать над массивами большущих размеров. Итак, давайте разобьем массив на $$$k$$$ блоков длины $$$n/k$$$. Будем хранить $$$k$$$ векторных массивов, то есть

vector<int>b[k];

Далее, при инициализации элементов массива $$$a$$$, будем добавлять $$$a_i$$$ в блок с номером $$$b[i/k]$$$. Затем, после добавления всех элементов, отсортируем каждый блок по неубыванию. Массив $$$a$$$ должен быть нулевой индексации.

Отвечаем на запросы на готовом упрощенном массиве.

1-й вид запросов На тех блоках, которые полностью входят в наш отрезок $$$[a,b]$$$, мы будем просто делать бинарный поиск. И $$$(n/k)-cnt(good)$$$ будет ответом на один из блоков, где $$$cnt(good)$$$ — количество не подходящих нам чисел, то есть тех, которые меньше $$$c$$$. Если же блок полностью не входит в отрезок, мы там просто в лоб пройдемся от позиции $$$a$$$ до позиции $$$(l1+1)*k-1$$$, где это первая позиция, относящаяся самому первому блоку слева. Аналогично сделаем и справа, где блок стоит правее, чем конечная позиция последнего блока.

2-й вид запросов Для выполнения такого запроса мы просто поменяем значение сначала $$$b[block][i]$$$, которое равно числу, стоящему на позиции $$$pos$$$ в массиве $$$a$$$, на значение $$$val$$$. $$$block$$$ — это номер блока, в котором находится $$$a_{pos}$$$. Затем меняем само значение $$$a_{pos}$$$ , и сортируем изменившийся блок.

К тому же, значения позиций в запросах нужно отнять на 1, так как индексация в массиве начинается с нуля.

КОД:

#include <bits/stdc++.h>
using namespace std;
const long long maxn=5e5+1;
int n,q,a[maxn],k=400;
vector<int>b[maxn];
int main(){
       cin>>n;
       for(int i=0;i<n;i++){
              cin>>a[i];
              b[(i/k)].push_back(a[i]);
       }
       for(int i=0;i<(n/k);i++){
              sort(b[i].begin(),b[i].end());
       }
       cin>>q;
       while(q--){
              int t;
              cin>>t;
              if(t==1){
                     int pos,val;
                     cin>>pos>>val;
                     pos--;
                     int bl=pos/k;
                     for(int i=0;i<b[bl].size();i++){
                            if(b[bl][i]==a[pos]){
                                   b[bl][i]=val;
                                   break;
                            }
                     }
                     a[pos]=val;
                     sort(b[bl].begin(),b[bl].end());
              } else{
                     int l,r,val;
                     cin>>l>>r>>val;
                     l--,r--;
                     int b1=l/k,b2=r/k,res=0;
                     if(b1==b2){
                            for(int i=l;i<=r;i++){
                                   if(a[i]>=val) res++;
                            }
                     }
                     else{
                            for(int i=b1+1;i<b2;i++){
                                   int pos=lower_bound(b[i].begin(),b[i].end(),val)-b[i].begin();
                                   res+=(b[i].size()-pos);
                            }
                            for(int i=l;i<=((b1+1)*k)-1;i++){
                                   if(a[i]>=val) res++;
                            }
                            for(int i=b2*k;i<=r;i++){
                                   if(a[i]>=val) res++;
                            }
                     }
                     cout<<res<<'\n';
              }
       }
}