HackerEarth Rhezo and his array problem solution YASH PAL, 31 July 2024 In this HackerEarth Rhezo and his array problem solution, Rhezo got an array A as a gift from his friend Tanya. Along with this array, she also gave him a list of operations to perform on the array. The operations that are present in the list are the following. Three integers L, R, and X are known, and Rhezo multiplies all numbers in the range [L, R] by X. Four integers L, R, X, and Y are known, and Rhezo needs to find out the count of integers in the range [L, R] whose product with X gives a number greater than or equal to Y. Now, you being Rhezo’s friend, have to help him in simulating the Q operations and report the answer to any operation of type 2. Please help poor Rhezo! HackerEarth Rhezo and his array problem solution. #include<bits/stdc++.h>using namespace std;#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds;#define ordered_set tree<pair<ll,int>, null_type, less< pair<ll,int> >, rb_tree_tag, tree_order_statistics_node_update>#define ff first#define ss second#define pb push_back#define mp make_pair#define all(x) x.begin(),x.end()#define sz(x) ((int)x.size())#define eps 1e-9const int MOD = 1e9+7;typedef long long ll;typedef pair<int,int> pii;ll POWER[65];ll power(ll a, ll b) {ll ret=1;while(b) {if(b&1) ret*=a;a*=a;if(ret>=MOD) ret%=MOD;if(a>=MOD) a%=MOD;b>>=1;}return ret;}ll inv(ll x) {return power(x,MOD-2);}void precompute() { POWER[0]=1; for(int i=1;i<63;i++) POWER[i]=POWER[i-1]<<1LL;}const int MAXN = 1e5+5;bool is[4*MAXN];ll ar[MAXN];ordered_set v[4*MAXN];const ll INF = 1000005000;bool overflow(ll x, ll y) { ll val = (INF+y-1)/y; if(x>=val) return true; return false;}void go(int idx, pair<ll,int> f1, pair<ll,int> f2) { while(idx) { v[idx].erase(f1); v[idx].insert(f2); idx/=2; }}void build(int node, int start, int end) { v[node].clear(); is[node]=false; if(start==end) { v[node].insert(mp(ar[start],start)); return; } int mid=(start+end)>>1; build(2*node,start,mid); build(2*node+1,mid+1,end); int oth=2*node,prim=2*node+1; if(sz(v[prim])<sz(v[oth])) swap(prim,oth); v[node]=v[prim]; for(auto it:v[oth]) v[node].insert(it);}void multiply(int node, int start, int end, int qs, int qe, ll val) { if(start>end or qe<start or qs>end) return; if(is[node]) return; if(start==end) { if(overflow(ar[start],val)) { is[node]=true; go(node,mp(ar[start],start),mp(INF,start)); ar[start]=INF; return; } go(node,mp(ar[start],start),mp(ar[start]*val,start)); ar[start]*=val; return; } int mid=(start+end)>>1; multiply(2*node,start,mid,qs,qe,val); multiply(2*node+1,mid+1,end,qs,qe,val); is[node]=is[2*node]&is[2*node+1];}int query(int node, int start, int end, int qs, int qe, ll val) { if(start>end or qe<start or qs>end) return 0; if(start>=qs and end<=qe) return end-start+1-v[node].order_of_key(mp(val,0)); int mid=(start+end)>>1; return query(2*node,start,mid,qs,qe,val)+ query(2*node+1,mid+1,end,qs,qe,val);}int main() { precompute(); int n,q; cin>>n>>q; assert(n>=1 and n<=50000); assert(q>=1 and q<=100000); for(int i=1;i<=n;i++) scanf("%lld",&ar[i]); build(1,1,n); while(q--) { int type,l,r; scanf("%d%d%d",&type,&l,&r); assert(type==1 or type==2); assert(l>=1 and l<=n); assert(r>=1 and r<=n); ll x,y; scanf("%lld",&x); assert(x>=2 and x<=1000000000); if(type==1) multiply(1,1,n,l,r,x); if(type==2) { ll y; scanf("%lld",&y); assert(y>=1 and y<=1000000000); printf("%dn",query(1,1,n,l,r,(y+x-1)/x)); } } return 0;} coding problems