社区讨论
线段树。。。真的没有人帮忙看一下吗。。
P1531I Hate It参与者 4已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi7wxtyf
- 此快照首次捕获于
- 2025/11/21 04:58 4 个月前
- 此快照最后确认于
- 2025/11/21 04:58 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,a[800005],x,y;
char f;
struct SegmentTree{
int l,r,data;
}t[800005];
void build(int p,int l,int r){
t[p].l=l;
t[p].r=r;
if (l==r) {
t[p].data=a[l];
return;
}
int mid=(l+r)/2;
build (p*2,l,mid);
build (p*2+1,mid+1,r);
t[p].data=max(t[p*2].data,t[p*2+1].data);
}
int ask(int p,int l,int r){
if (t[p].l>=l&&t[p].r<=r) return t[p].data ;
int mid=(l+r)/2,tmp=0;
if (l<=mid) tmp=max(tmp,ask(2*p,l,r));
if (r>mid) tmp=max(tmp,ask(2*p+1,l,r));
return tmp;
}
void change(int p,int x,int v){
//如果当前节点为叶节点,更新节点即data 该区间的最大值
if (t[p].l==t[p].r){
t[p].data=max(t[p].data,v);
return;
}
//递归进入左右节点,同时自下而上更新相应节点区间
int mid=(t[p].l+t[p].r)/2;
if (x<=mid) change(2*p,x,v);
else change(2*p+1,x,v);
//自下而上更新
t[p].data=max(t[2*p].data,t[2*p+1].data);
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
build (1,1,n);
for (int i=1;i<=m;i++){
cin>>f>>x>>y;
if (f=='Q') printf("%d\n",ask(1,x,y));
else change(1,x,y);
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...