HackerEarth Operations on an array problem solution

In this HackerEarth Operations on an array problem solution, 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 << "-1n";;
                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 << "-1n";
            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);
        }
    }
}

coding problems solutions