hihoCoder week19 RMQ问题再临-线段树 单点更新 区间查询

#include <bits/stdc++.h>

using namespace std;

#define m ((l+r)/2)

#define ls (rt<<1)

#define rs (rt<<1|1)

const int N = 2e6+;

int s[N], tr[N];

void build(int rt,int l,int r)

{

    if(l == r) {

        tr[rt] = s[l];

        return ;

    }

    build(ls, l, m);

    build(rs, m+, r);

    tr[rt] = min(tr[ls], tr[rs]);

}

void update(int rt,int l,int r,int pos,int val)

{

    if(l == r && l == pos) {

        tr[rt] = val;

        return ;

    }

    if(pos <= m)

        update(ls, l, m, pos, val);

    else

        update(rs, m+, r, pos, val);

    tr[rt] = min(tr[ls], tr[rs]);

}

int query(int rt,int l,int r,int L,int R)

{

    if(L<=l && r<=R) {

        return tr[rt];

    }

    int res = 0x3f3f3f3f;

    if(L <= m)

        res = min(res, query(ls,l,m,L,R));

    if(R > m)

        res = min(res, query(rs,m+,r,L,R));

    return res;

}

void out(int rt,int l,int r)

{

    printf("%d %d %d\n", l, r, tr[rt]);

    if(l == r ) {

        return ;

    }

    out(ls, l, m);

    out(rs, m+, r);

}

int main()

{

    freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n; scanf("%d", &n);

    for(int i=; i<=n; i++) {

        scanf("%d", &s[i]);

    }

    build(,,n);

    // out(1,1,n);

    int t; scanf("%d", &t);

    while(t--) {

        int op,l,r;

        scanf("%d %d %d", &op, &l, &r);

        if(op) {

            update(,,n,l,r);

            //out(1,1,n);

        }

        else {

            printf("%d\n", query(,,n,l,r));

        }

        // out(1,1,n);

    }

    return ;

}