蒟蒻求助线段树裸题

回复帖子

@翼德天尊  2020-08-02 10:56 回复

调了快一上午了……求助各位大佬QwQ

对着题解改了改,但是改了半天还是不对。

评测记录

代码如下(加上了注释):

#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 10005
int t_,n,wi,hi,q,lsh[MAXN<<1],tlsh;
struct node{//询问 
    int l,r,w,a;
    node(int l=0,int r=0,int w=0,int s=0)
        :l(l),r(r),w(w),a(s){}
}e[MAXN<<1];
struct node1{//线段树 
    int l,r,maxn,lz;
}t[MAXN<<3];
int read(){//快读 
    int w=0,f=1;
    char c=getchar();
    while (c>'9'||c<'0'){
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9'){
        w=(w<<3)+(w<<1)+(c^48);
        c=getchar();
    }
    return w*f;
}
bool cmp(node x_,node y_){//自定义排序 
    if (x_.w==y_.w) return x_.a>y_.a;
    return x_.w<y_.w;
}
void build(int i,int l,int r){//建树 
    t[i].l=l,t[i].r=r,t[i].maxn=t[i].lz=0;
    if (l==r){
        return;
    }
    int mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r); 
}
void push_down(int i){//下传 
    if (t[i].lz){
        t[i<<1].lz+=t[i].lz;
        t[i<<1|1].lz+=t[i].lz;
        t[i<<1].maxn+=t[i].lz;
        t[i<<1|1].maxn+=t[i].lz;
        t[i].lz=0; 
    }
} 
void add(int i,int l,int r,int k){//扫描 
    if (t[i].l>=l&&t[i].r<=r){
        t[i].maxn+=k;
        t[i].lz+=k;
        return;
    }
    push_down(i);
    if (t[i<<1].r>=l) add(i<<1,l,r,k);
    if (t[i<<1|1].l<=r) add(i<<1|1,l,r,k);
    t[i].maxn=max(t[i<<1].maxn,t[i<<1|1].maxn);
}
int main(){
    t_=read();
    while (t_--){
        int ans=0;
        tlsh=q=0;
        n=read(),wi=read()-1,hi=read()-1;
        for (int i=1;i<=n;i++){
            int x=read(),y=read(),a=read();
            e[++q]=node(y,y+hi,x,a);
            e[++q]=node(y,y+hi,x+wi,-a);//处理询问 
            lsh[++tlsh]=y,lsh[++tlsh]=y+hi-1; 
        } 
        sort(lsh+1,lsh+1+tlsh);
        int g=unique(lsh+1,lsh+1+n)-lsh-1;//离散化 
        sort(e+1,e+1+q,cmp);//排序 
        build(1,1,n);
        for (int i=1;i<=q;i++){
            int l=lower_bound(lsh+1,lsh+1+g,e[i].l)-lsh;
            int r=lower_bound(lsh+1,lsh+1+g,e[i].r)-lsh;//离散化 
            add(1,l,r,e[i].a);
            ans=max(ans,t[1].maxn);
        }
        printf("%d\n",ans);
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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