https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/C
I am getting wrong answer at input
2 3
1 1 0
2 1 2
I think query function is not working properly as it is returning INT_MAX what should i write to make it correct plz help
#include<bits/stdc++.h>
#include<assert.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
#define Fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(0);
#define fo(i,s,n) for(int i=s;i<n;i++)
#define mod 1000000007
#define umap unordered_map
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define lb() lower_bound()
#define ub() upper_bound()
#define PI 3.14159265
#define S second
#define F first
//fill(all(vec), 1);to fill vector with a number
//if (S.count(key)) returns 1 if set or map contain key else return 0
ll nCr(ll n,ll r)
{
r = min(r,n-r);
if(r<0)
return 0;
if(r == 0)
return 1;
ll ans = 1;
for(ll i = 1;i<=r;i++)
{
ans = ans*(n-i+1)/i;
}
return ans;
}
ll logn(int n, int r)
{
return (n > r - 1) ? 1 + logn(n / r, r) : 0;
}
ll power(ll a,ll b) {
if(b == 1) return a;
if(b == 0) return 1;
ll m1 = power(a,b/2);
if(b%2) return m1*m1*a;
return m1*m1;
}
bool isprime(ll a)
{
if(a<=1)
return false;
if(a==2||a==3)
return true;
if(a%2==0||a%3==0)
return false;
for(ll i=5;i*i<=a;i=i+6)
{
if(a%i==0||a%(i+2)==0)
return false;
}
return true;
}
/*********************//*********************///*********************///*********************//
ll t;
vector<pair<ll,ll>>tree(10000005);//(4*n,make_pair(0,0));
void built(ll s,ll e,ll index,ll *a)
{
if(s>e)
return;
if(s==e)
{
tree[index].first=a[s];
tree[index].second=1;
return;
}
ll mid=(s+e)/2;
built(s,mid,2*index+1,a);
built(mid+1,e,2*index+2,a);
tree[index].F=min(tree[2*index+1].F,tree[index*2+2].F);
if(tree[2*index+1].F==tree[index*2+2].F)
{
tree[index].S=tree[index*2+2].S+tree[2*index+1].S;
}
else
{
if(tree[2*index+1].F<tree[2*index+2].F)
tree[index].S=tree[2*index+1].S;
else
{
tree[index].S=tree[2*index+2].S;
}
}
return;
}
pair<ll,ll> query(ll s,ll e,ll index,ll qs,ll qe)
{
if(qs>=e||qe<=s)
return {INT_MAX,0};
if(qs<=s&&qe>=e)
return tree[index];
ll mid=(s+e)/2;
pair<ll,ll> l=query(s,mid,2*index+1,qs,qe);
pair<ll,ll> r=query(s,mid,2*index+1,qs,qe);
if(l.F<r.F)
{
return l;
}
else
{
return r;
}
}
void update(ll s,ll e,ll index,ll i,ll val)
{
if(i<s||i>e)
return;
if(s==e)
{
//if(tree[index])
tree[index].F=val;
tree[index].S=1;
return;
}
ll mid=(s+e)/2;
update(s,mid,2*index+1,i,val);
update(mid+1,e,2*index+2,i,val);
pair<ll,ll> l=tree[2*index+1];
pair<ll,ll> r=tree[2*index+2];
if(l.F==r.F)
{
tree[index].F=l.F;
tree[index].S=l.S+r.S;
}
else if(l.F<r.F)
{
tree[index].first=l.F;
tree[index].S=l.S;
}
else
{
/* code */
tree[index].first=r.F;
tree[index].S=r.S;
}
return;
}
void solve()
{
ll n,q;
cin>>n>>q;
ll a[n];
fo(i,0,n)
cin>>a[i];
/*fo(i,0,4*n)
{
tree[i].F=0;
tree[i].S=0;
}*/
/*fo(i,0,4*n)
{
cout<<tree[i].F<<'-'<<tree[i].S<<" ";
}*/
built(0,n-1,0,a);
while(q--)
{
int tem;
cin>>tem;
if(tem==2)
{
ll qs,qe;
cin>>qs>>qe;
qe--;
pair<ll,ll>x=query(0,n-1,0,qs,qe);
cout<<x.F<<" "<<x.second<<endl;
}
else
{
ll i,val;
cin>>i>>val;
update(0,n-1,0,i,val);
}
}
/*
fo(i,0,4*n)
{
cout<<tree[i].F<<'-'<<tree[i].S<<" ";
}
cout<<endl;*/
}
int main()
{
Fast
/*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
*/
//cin>>t;
t=1;
for(ll i=1;i<=t;i++)
{
solve();
}
return 0;
}