In this HackerEarth Operations on an array problem, You are given an array of n elements and an integer x. You must perform the following types of operations on the array:

Find the index of the kth occurrence of x in the range l to r (both inclusive). If there are no indexes that satisfy the condition, then print -1.
Update the value that is present at the given index.
For each query of type 1, print the index of the kth occurrence of x.

## HackerEarth Operations on an array problem solution.

```#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int N = 1000000 + 1;
int arr[N];
struct BIT{//use one based indexing
int N;
vector<int> bit;

void init(int n){
bit.clear();
N = n + 9;
bit.assign(n + 10, 0);
}

void update(int idx, int val){
while(idx <= N){
bit[idx] += val;
idx += idx & -idx;
}
}

int pref(int idx){
int ans = 0;
while(idx > 0){
ans += bit[idx];
idx -= idx & -idx;
}
return ans;
}

int rsum(int l, int r){
return pref(r) - pref(l - 1);
}

int kthOrder(int k){
if(pref(N - 1) < k){
return -1;
}
int cur = 0,sum = 0, ExtraSize = N;
int ln = log2(ExtraSize);
for(int i = ln;i >= 0 ; --i){
int temp = cur + (1 << i);
if((temp < ExtraSize) && (sum + bit[temp]) < k){
cur = temp;
sum += bit[temp];
}
}
return cur + 1;
}

//one based indexing
int lower_bound(int val){
return (pref(val - 1) + 1);
}
//one based indexing
int upper_bound(int val){
return (pref(val) + 1);
}
}bt;
signed main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int n,x;
cin >> n >> x;
bt.init(n);
for(int i = 1;i <= n;i++){
cin >> arr[i];
if(arr[i] == x){
bt.update(i,1);
}
}
int q;
cin >> q;
while(q--){
int type;
cin >> type;
if(type == 1){
int l,r,k;
cin >> l >> r >> k;
k += bt.pref(l - 1);
if(k > bt.pref(r)){
cout << "-1\n";;
continue;
}
cout << bt.kthOrder(k) << "\n";
}else{
int l,val;
cin >> l >> val;
if(arr[l] == x){
bt.update(l,-1);
}
if(val == x){
bt.update(l,1);
}
arr[l] = val;
}
}
}```

### Second solution

```#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> os;
typedef long long ll;
const int maxn = 1e6 + 14, mod = 1e9 + 7;

int n, a[maxn], x;
int pos(int p){
auto s = os.lower_bound(p);
if(s == os.end())
return os.size();
return os.order_of_key(p);
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> x;
for(int i = 0; i < n; i++){
cin >> a[i];
if(a[i] == x)
os.insert(i);
}
int q;
cin >> q;
while(q--){
int t;
cin >> t;
if(t == 1){
int l, r, k;
cin >> l >> r >> k;
l--, k--;
if(pos(l) == n || pos(l) + k >= pos(r))
cout << "-1\n";
else
cout << *os.find_by_order(pos(l) + k) + 1 << '\n';
}
else{
int i, v;
cin >> i >> v;
i--;
if(a[i] == x)
os.erase(i);
a[i] = v;
if(a[i] == x)
os.insert(i);
}
}
}```