CSES - Shared codeLink to this code:
https://cses.fi/paste/7452d61222a6b9589745b9/
#include <bits/stdc++.h>
using namespace std;
struct node{
long ml=100000000000L;
long mr=10000000000L;
long sz=0;
};
node merge(node a, node b){
node t;
t.ml=min(a.ml, b.ml+a.sz);
t.mr=min(a.mr+b.sz, b.mr);
t.sz=a.sz+b.sz;
return t;
}
class segTree{
vector<node> tr;
int N=1;
public:
segTree(int n){
while(N<n)
N*=2;
for(int i=0; i<N*2; i++)
{
node t;
t.sz=1;
tr.push_back(t);
}
}
void update(int a, int v){
a+=N;
tr[a].ml=v;
tr[a].mr=v;
while(a>1)
{
a/=2;
tr[a]=merge(tr[a*2], tr[a*2+1]);
}
}
long squery(int ind){
return min(query(0, ind).mr, query(ind, N-1).ml);
}
node query(int l, int r){
node t;
node tp;
l+=N; r+=N;
//cout<<l<<' '<<r<<"?"<<endl;
while(l<r){
if(l%2==1)
t=merge(t,tr[l++]);
if(r%2==0)
tp=merge(tr[r--], tp);
l/=2; r/=2;
//cout<<t.va<<' '<<tp.va<<endl;
//cout<<l<<' '<<r<<endl;
}
if(l==r){
t=merge(t, tr[l]);
}
return merge(t,tp);
}
};
int main() {
cin.tie(NULL);
int N,Q; cin>>N>>Q;
segTree tr(N);
for(int i=0; i<N; i++)
{
int t; cin>>t;
tr.update(i, t);
}
while(Q--){
int t,a,b; cin>>t;
if(t==2){
cin>>a;
cout<<tr.squery(a-1)<<"\n";
}
else{
cin>>a>>b;
tr.update(a-1,b);
}
}
cout<<flush;
}