HackerEarth Operations on an array problem solution YASH PAL, 31 July 2024 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