algorithm - 範囲 [l,r] で値 a[x]>u である最初のインデックス x を見つけます

Question

与えられた配列 a[]にはn 個の非負の要素があります。2 種類のクエリがあります。

A xyv : a[i]>v である最初のインデックス i (x<=i<=y) を見つけます

B uv : a[u]=v; を更新します。

セグメント ツリーを使用していますが、一部のテストでは TLE です。

これは私のコードです。

it max(it A,it B)
{
    it C;
    C.mx=max(A.mx,B.mx);
    return C;
}

これは、最初のツリーを構築する関数です。

void build(int id,int l,int r)
{
    if(l==r)
    {
        st[id].mx=a[l];
        st[id].pos=l;
        return;
    }
    int m=l+r>>1;
    build(id<<1,l,m);
    build(id<<1|1,m+1,r);
    st[id]=max(st[id<<1],st[id<<1|1]);
}

更新クエリ:

void update(int id,int l,int r,int u,int v)
{
    if(u<l||r<u) return;
    if(l==r)
    {
        st[id].mx=v;
        return;
    }
    int m=l+r>>1;
    update(id<<1,l,m,u,v);
    update(id<<1|1,m+1,r,u,v);
    st[id]=max(st[id<<1],st[id<<1|1]);
}

「検索」クエリ:

int getmin(int id,int l,int r,int u,int v,int value)
{
    if(v<l||r<u) return 1e9;
    if(l==r)
    {
        return st[id].pos;
    }
    int m=l+r>>1;
    //cout<<"->"<<id<<" "<<l<<" "<<r<<endl;
    if(st[id<<1].mx<=value)
    {
        if(st[id<<1|1].mx<=value)
            return 1e9;
        else return getmin(id<<1|1,m+1,r,u,v,value);
    }
    else
    {
        if(st[id<<1|1].mx<=value)
            return getmin(id<<1,l,m,u,v,value);
        else return min(getmin(id<<1,l,m,u,v,value),getmin(id<<1|1,m+1,r,u,v,value));
    }
}