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.
  1. Three integers L, R, and X are known, and Rhezo multiplies all numbers in the range [L, R] by X.
  2. 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


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-9

const 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("%d\n",query(1,1,n,l,r,(y+x-1)/x));
}
}
return 0;
}