求助!

回复帖子

@黄耀风 2021-04-08 14:05 回复

题目大意:有 $n$ 个数, $m$ 个操作,每个操作形如 l r v 表示将区间 $[l,r]$ 中的最大值(如果有多个则取编号最小的)减去 $v$。

最后输出整个数列。

数据范围: $1 \leq n,m \leq 5 \times 10^4$。

如上,线段树调假了, $90$ 分,一个点 MLE。

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int maxnum;
    int id;
}tree[2000001];
int n,m;
int a[500001];
void build(int l,int r,int p){
    if(l==r){
        tree[p].maxnum=a[l];
        tree[p].id=l;
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    if(tree[p*2].maxnum>=tree[p*2+1].maxnum){
        tree[p].maxnum=tree[p*2].maxnum;
        tree[p].id=tree[p*2].id;
    }
    else{
        tree[p].maxnum=tree[p*2+1].maxnum;
        tree[p].id=tree[p*2+1].id;
    }
    return;
}
int get_max(int l,int r,int nowl,int nowr,int p){//求区间最大值
    if(l<=nowl&&nowr<=r){
        return tree[p].maxnum;
    }
    int mid=(nowl+nowr)/2,maxnum=-100000000;
    if(mid>=l) maxnum=max(maxnum,get_max(l,r,nowl,mid,p*2));
    if(mid<r) maxnum=max(maxnum,get_max(l,r,mid+1,nowr,p*2+1));
    return maxnum;
}
int get_id(int l,int r,int nowl,int nowr,int p){//求区间最大值的下标
    if(l<=nowl&&nowr<=r){
        return tree[p].id;
    }
    int mid=(nowl+nowr)/2,maxnum=-100000000,maxid=-10000000;
    if(mid>=l){
        int lmax=get_max(l,r,nowl,mid,p*2);
        if(lmax>=maxnum){
            maxnum=lmax;
            maxid=get_id(l,r,nowl,mid,p*2);
        }
    }
    if(mid<r){
        int rmax=get_max(l,r,mid+1,nowr,p*2+1);
        if(rmax>maxnum){
            maxnum=rmax;
            maxid=get_id(l,r,mid+1,nowr,p*2+1);
        }
    }
    return maxid;
}
void update(int l,int r,int nowl,int nowr,int k,int p){
    if(l<=nowl&&nowr<=r){
        tree[p].maxnum+=k;
        return;
    }
    int mid=(nowl+nowr)/2;
    if(mid>=l) update(l,r,nowl,mid,k,p*2);
    if(mid<r) update(l,r,mid+1,nowr,k,p*2+1);
    if(tree[p*2].maxnum>=tree[p*2+1].maxnum){
        tree[p].maxnum=tree[p*2].maxnum;
        tree[p].id=tree[p*2].id;
    }
    else{
        tree[p].maxnum=tree[p*2+1].maxnum;
        tree[p].id=tree[p*2+1].id;
    }
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,n,1);
    while(m--){
        int l,r,v;
        cin>>l>>r>>v;
        int id=get_id(l,r,1,n,1);//记录最大值的下标
        update(id,id,1,n,-v,1);
    }
    for(int i=1;i<=n;i++){
        cout<<get_max(i,i,1,n,1)<<" ";
    }
}

谢谢!

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。