【TYVJ】P1039 忠诚2

【算法】线段树

【注意】修改或查询区间时，若区间能包含某棵子树就立即返回，否则线段树就失去了意义。

#include<cstdio>

#include<algorithm>

using namespace std;

const int inf=0x3f3f3f3f;

struct treess{int l,r,ms;}t[];

int a[],n,m,tot,anss[];

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

{

    t[k].l=l;t[k].r=r;

    if(l==r){t[k].ms=a[l];return;}

    int mid=(l+r)>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    t[k].ms=min(t[k<<].ms,t[k<<|].ms);

//    printf("[%d] l=%d r=%d mins=%d\n",k,t[k].l,t[k].r,t[k].ms);

}

void insert(int k,int x,int y)

{

    int left=t[k].l,right=t[k].r;

    if(left==right)t[k].ms=y;

     else

      {

          int mid=(left+right)>>;

          if(x<=mid)insert(k<<,x,y);

          else insert(k<<|,x,y);

        t[k].ms=min(t[k<<].ms,t[k<<|].ms);

      }

}

int ask(int k,int l,int r)

{

    int left=t[k].l,right=t[k].r;

    if(l<=left&&right<=r)return t[k].ms;

     else

      {

          int mid=(left+right)>>,ans=inf;

          if(l<=mid)ans=ask(k<<,l,r);

          if(r>mid)ans=min(ans,ask(k<<|,l,r));

          return ans;

      }

}

int main()

{

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

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    build(,,n);

    for(int i=;i<=m;i++)

     {

         int p,x,y;

         scanf("%d%d%d",&p,&x,&y);

         if(p==)anss[++tot]=ask(,x,y);

          else insert(,x,y);

     }

    for(int i=;i<tot;i++)printf("%d ",anss[i]);

    printf("%d",anss[tot]);

    return ;

}