Dynamic Range Minimum Queries

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4constexpr int SZ=447,INF=3e18;
5signed main(){
6  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
7  int n,q; cin>>n>>q;
8  int x[n]; for(int i=0;i<n;++i) cin>>x[i];
9  int m=(n+SZ-1)/SZ,mn[m]; fill(mn,mn+m,INF);
10  for(int i=0;i<n;++i){
11    int j=i/SZ;
12    mn[j]=min(mn[j],x[i]);
13  }
14  while(q--){
15    int t,a,b; cin>>t>>a>>b;
16    if(t==1){
17      int j=--a/SZ;
18      x[a]=b,mn[j]=INF;
19      for(int i=j*SZ;i<min(n,(j+1)*SZ);++i){
20        mn[j]=min(mn[j],x[i]);
21      }
22    }else{
23      int res=INF,i=--a/SZ,j=--b/SZ;
24      if(i==j) for(int k=a;k<=b;++k) res=min(res,x[k]);
25      else{
26        for(int k=a;k<(i+1)*SZ;++k) res=min(res,x[k]);
27        for(int k=i+1;k<j;++k) res=min(res,mn[k]);
28        for(int k=j*SZ;k<=b;++k) res=min(res,x[k]);
29      }
30      cout<<res<<'\n';
31    }
32  }
33  return 0;
34}