社区讨论

线段树。。。真的没有人帮忙看一下吗。。

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 条回复,欢迎继续交流。

正在加载回复...