题目
1 x d 修改 ax=d
2 l r 查询l r区间内的最小值并计算区间内最小值出现了多少次
#include<bits/stdc++.h>
using namespace std;
#define maxn 201000
int n,q;
int a[maxn];
struct info
{
int minv,mincnt;
};
info operator + (const info &l, const info &r)//重载加法
{
info a;
a.minv = min(l.minv,r.minv);
if(l.minv==r.minv) a.mincnt=l.mincnt+r.mincnt;//左右两边最小值一样,直接加
else if (l.minv<r.minv) a.mincnt=l.mincnt;
else a.mincnt = r.mincnt;
return a;
}
struct node
{
info val;
}seg[maxn*4];//一般开成四倍
void update(int id)
{
seg[id].val=seg[id*2].val+seg[id*2+1].val;
}//更新节点的信息
void build(int id,int l,int r)//编号是id,l到r这个区间
{
if(l==r)
{
seg[id].val={a[l],1};
}
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].val={val,1};//权值大小是val 出现次数是1
}//是叶节点
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
info query(int id,int l,int r,int ql,int qr)//ql qr 表示查询的区间
{
if(l==qr&&r==qr)
{
return seg[id].val;
}
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 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;
auto ans=query(1,1,n,l,r);
cout<<ans.minv<<" "<<ans.mincnt<<endl;
}
}
return 0;
}