Number of Minimums on a Segment

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007;

#define got cout<<"Yes\n"; return;
#define got0 cout<<"Yes\n"; return 0;

#define bhak cout<<"No\n"; return;
#define bhak0 cout<<"No\n"; return 0;

#define bas cout<<"\n";


pair<ll,ll> constructTree(ll ts, ll te, ll ti, vector<pair<ll,ll>> &tree, vector<ll> &vec){
    if(ts==te){
        return tree[ti] = {vec[ts], 1};
    }

    ll mid = ts + (te-ts)/2;

    pair<ll,ll> left = constructTree(ts, mid, 2*ti+1, tree, vec);
    pair<ll,ll> right = constructTree(mid+1, te, 2*ti+2, tree, vec);

    ll mini = min(left.first, right.first);

    ll ct=0;

    if(mini == left.first){
        ct+= left.second;
    }

    if(mini == right.first){
        ct += right.second;
    }

    return tree[ti] = {mini, ct};

}

void printTree(vector<pair<ll,ll>> &tree){
    ll ct = 0;
    ll maxi = 1;
    for(auto a : tree){
        cout<<"("<<a.first<<","<<a.second<<")"<<" ";

        ct++;
        if(maxi==ct){
            maxi *=2;
            ct=0;
            bas
        }
    }
}


pair<ll,ll> getMini(ll ts, ll te, ll rs, ll re, ll ti, vector<pair<ll,ll>> &tree){
    if(te<rs || ts>re){
        return {1e12, 1e12};
    }

    cout<<"Mini Target: ("<<rs<<","<<re<<") Moving to ("<<ts<<","<<te<<")"; bas

    if(ts>=rs && te<=re){
        return tree[ti];
    }


    if(te==ts){
        return tree[ti];
    }

    ll mid = ts + (te-ts)/2;

    return min(
                getMini(ts, mid, rs, re,  2*ti+1, tree),
                getMini(mid+1, te, rs, re,  2*ti+2, tree)
        );
}

pair<ll,ll> update(ll ts, ll te, ll ti, ll tar, ll val, vector<pair<ll,ll>> &tree){
    if(tar>te || tar<ts){
        return tree[ti];
    }

    // cout<<"Update Target is "<<tar<<" moving to ("<<ts<<","<<te<<")"; bas

    if(ts==te){
        if(ts==tar){
            tree[ti] = {val, 1};
        }

        return tree[ti];
    }


    ll mid = ts + (te-ts)/2;

    pair<ll,ll> left = update(ts, mid, 2*ti+1, tar, val, tree);
    pair<ll,ll> right = update(mid+1, te, 2*ti+2, tar, val, tree);

    ll mini = min(left.first, right.first);

    ll ct=0;

    if(mini == left.first){
        ct+= left.second;
    }

    if(mini == right.first){
        ct += right.second;
    }

    return tree[ti] = {mini, ct};
}

int main() {
    ll n, m; cin>>n>>m;
    vector<ll> vec(n);

    for(ll i=0; i<n; ++i){
        cin>>vec[i];
    }

    vector<pair<ll,ll>> tree(4*n);

    constructTree(0, n-1, 0, tree, vec);

    // printTree(tree);

    while(m--){
        ll a, b, c;
        cin>>a>>b>>c;

        if(a==1){
            update(0, n-1, 0, b, c, tree);
        }
        else if(a==2){
            // printTree(tree);
            pair<ll,ll> ans = getMini(0, n-1, b, c-1, 0, tree);
            cout<<ans.first<<" "<<ans.second; bas
        }
    }



    return 0;
}