题目描述
1 x y 代表把x这个数改成y
2 l r 代表查找l r区间的最小值
#include<bits/stdc++.h>
using namespace std;
#define maxn 201000
int n,q;
int a[maxn];
struct node
{
int minv;//表示区间内的最小值
}seg[maxn*4];//一般开成四倍
void update(int id)
{
seg[id].minv=min(seg[id*2].minv,seg[id*2+1].minv);
}//更新节点的信息
void build(int id,int l,int r)//编号是id,l到r这个区间
{
if(l==r)
{
seg[id].minv=a[l];
}
else
{
int mid=(l+r)>>1;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
update(id);
}
}
void change(int id,int l,int r,int pos,int val)
{
if(l==r)
{
seg[id].minv=val;
}//是叶节点
else
{
int mid=(l+r)>>1;
if(pos<=mid)
change(id*2,l,mid,pos,val);
else
change(id*2+1,mid+1,r,pos,val);
update(id);//左右节点会有修改,更新这个节点的信息
}
}//单点修改。节点编号为id,对应的区间为l,r,修改a[pos] -> val
int query(int id,int l,int r,int ql,int qr)//ql qr 表示查询的区间
{
if(l==qr&&r==qr)
{
return seg[id].minv;
}
int mid=(l+r)>>1;
if(qr<=mid)//如果整个都在左边,返回左边的查询结果
{
return query(id*2,l,mid,ql,qr);
}
else if(ql>mid) return query(id*2+1,mid+1,r,ql,qr);
else
{
//qr>mid,ql<=mid
//[ql,mid] [mid+1,qr]
return min(query(id*2,l,mid,ql,mid)
,query(id*2+1,mid+1,r,mid+1,qr));
}
}
int main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
for(int i=0;i<q;i++)
{
int op;
cin>>op;
if(op==1)
{
int x,d;
cin>>x>>d;
change(1,1,n,x,d);
}
else
{
int l,r;
cin>>l>>r;
cout<<query(1,1,n,l,r)<<endl;
}
}
return 0;
}