扫描线洛谷1502

短命女 2023-08-17 15:44 110阅读 0赞

这傻吊题，我也不知道自己为啥交了一页的0分代码。

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int M=20005;
    struct Node{int l,r,h,v;}line[M];
    struct node{int l,r;ll v,tag;}t[M<<2];
    int n,cnt,tot;
    ll b[M],w,h;
    bool cmp(Node a,Node b){return a.h==b.h?a.v>b.v:a.h<b.h;}
    void build(int k,int l,int r){
        t[k].l=l;t[k].r=r;t[k].tag=t[k].v=0;
        if(l==r)return ;
        int mid=(l+r)>>1;
        build(k*2,l,mid);
        build(k*2+1,mid+1,r);
    }
    void up(int k){ t[k].v=max(t[k*2].v,t[k*2+1].v);}
    void down(int k){
        if(t[k].tag){
            t[k*2].tag+=t[k].tag;t[k*2].v+=t[k].tag;
            t[k*2+1].tag+=t[k].tag;t[k*2+1].v+=t[k].tag;
            t[k].tag=0;
        }
    }
    void update(int k,int l,int r,ll v){
        if(l<=t[k].l&&t[k].r<=r){
            t[k].tag+=v;
            t[k].v+=v;
            return ;
        }
        down(k);
        int mid=(t[k].l+t[k].r)>>1;
        if(l<=mid)update(k*2,l,r,v);
        if(mid<r)update(k*2+1,l,r,v);
        up(k);
    }
    int main(){
        int T;scanf("%d",&T);
        for(int tt=1;tt<=T;tt++){
            cnt=tot=0;
            scanf("%d%lld%lld",&n,&w,&h);
            for(int x,y,v,i=1;i<=n;i++){
                scanf("%d%d%d",&x,&y,&v);
                b[++tot]=y;b[++tot]=y+h-1;
                line[++cnt].l=y;line[cnt].r=y+h-1;line[cnt].h=x;line[cnt].v=v;
                line[++cnt].l=y;line[cnt].r=y+h-1;line[cnt].h=x+w-1;line[cnt].v=-v;
            }
            n<<=1;sort(b+1,b+n+1);
            tot=1;for(int i=2;i<=n;i++)if(b[i]!=b[i-1])b[++tot]=b[i];
            sort(line+1,line+n+1,cmp);
            build(1,1,tot);
            for(int i=1;i<=n;i++){
                line[i].l=lower_bound(b+1,b+tot+1,line[i].l)-b;
                line[i].r=lower_bound(b+1,b+tot+1,line[i].r)-b;
            }
            ll res=0;
            for(int i=1;i<=n;i++){
                update(1,line[i].l,line[i].r,line[i].v);
                res=max(res,t[1].v);
            }
            printf("%lld\n",res);
        }
        return 0;
    }