计蒜客 管家的忠诚(二) 线段树

计蒜客 管家的忠诚(二) 线段树

老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。           在询问过程中账本的内容可能会被修改

输入中第一行有两个数m,n表示有m(m< =100000)笔账,n表示有n个问题，n< =100000。 接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y 当p=1  则查询x,y区间 当p=2  则改变第x个数为y

输出文件中为每个问题的答案。具体查看样例。

样例输入

10 3
1 2 3 4 5 6 7 8 9 10
1 2 7
2 2 0
1 1 10

样例输出

2 0

#include<stdio.h>  
#include<algorithm>
using namespace std;
#define MAXN 100005  int ans;  
struct node{  int left,right,minn;  int mid(){  return (left+right)>>1;  }  
}tree[MAXN*4];  void buildTree(int l,int r,int rt){  tree[rt].left = l;  tree[rt].right = r;  if(l==r){  scanf("%d",&tree[rt].minn);  return ;  }  int mid = tree[rt].mid();  buildTree(l,mid,rt<<1);  buildTree(mid+1,r,rt<<1|1);  tree[rt].minn = min(tree[rt<<1].minn , tree[rt<<1|1].minn);  
}  void query(int L,int R,int rt,int l,int r){  if(l<=L&&r>=R){   ans=min(ans,tree[rt].minn);  return ;  }  int mid = tree[rt].mid();  if(r<=mid){  query(L,mid,rt<<1,l,r);  }  else if(l>mid){  query(mid+1,R,rt<<1|1,l,r);  }  else{  query(L,mid,rt<<1,l,r);  query(mid+1,R,rt<<1|1,l,r);  }  
}  void update(int l,int r,int rt,int pos,int val){  if(l==r){   tree[rt].minn=val;  return;  }  int mid=tree[rt].mid();  if(pos<=mid){  update(l,mid,rt<<1,pos,val);  }  else{  update(mid+1,r,rt<<1|1,pos,val);  }  tree[rt].minn = min(tree[rt<<1].minn , tree[rt<<1|1].minn);  
}  int main(){  int t,n,m;  int a,b;  int x;      scanf("%d%d",&n,&m);  buildTree(1,n,1);int flag=0;   while(m--){  scanf("%d%d%d",&x,&a,&b); if(x==1){  ans=0x3fffffff;  query(1,n,1,a,b);if(flag==0){printf("%d",ans); flag=1;}  elseprintf(" %d",ans); }  else update(1,n,1,a,b);    } return 0;  
}