HackerEarth Rhezo and his array problem solution

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.

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