70分,求助
查看原帖
70分,求助
785700
封禁用户楼主2022/11/20 13:58
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fxt(i,x,y) for(int i=(x);i<=(y);i++)
#define pyt(i,x,y) for(int i=(x);i>=(y);i--)
const int N=1e4+5;
int T,n,w,h,ans;
struct matrix{int xl,yl,xr,yr,val;}sca[N];
int lsh[N*2],lh;
struct scan{
    int x,l,r,val;
    scan(){}
    scan(int a,int b,int c,int d){x=a;l=b;r=c;val=d;}
    bool operator < (scan a)const{
        if(x==a.x)return val>a.val;
        return x<a.x;
    }
}now[N*2];
struct XDS{
    #define ls x<<1
    #define rs x<<1|1
    int mx[N*8],tg[N*8];
    void pushup(int x){
        mx[x]=max(mx[ls],mx[rs]);
        return ;
    }
    void pushdown(int x){
        tg[ls]+=tg[x];
        tg[rs]+=tg[x];
        mx[ls]+=tg[x];
        mx[rs]+=tg[x];
        tg[x]=0;return ;
    }
    void build(int x,int l,int r){
        mx[x]=tg[x]=0;
        if(l==r)return ;
        int mid=l+r>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        return ;
    }
    void ins(int x,int l,int r,int ql,int qr,int v){
        if(ql<=l&&r<=qr){
            mx[x]+=v;tg[x]+=v;
            return ;
        }
        if(tg[x])pushdown(x);
        int mid=l+r>>1;
        if(ql<=mid)ins(ls,l,mid,ql,qr,v);
        if(qr>mid)ins(rs,mid+1,r,ql,qr,v);
        pushup(x);return ;
    }
    #undef ls
    #undef rs
}xds;
signed main(){
    scanf("%lld",&T);
    while(T--){
        lh=ans=0;
        scanf("%lld%lld%lld",&n,&w,&h);
        fxt(i,1,n){
            scanf("%lld%lld%lld",&sca[i].xl,&sca[i].yl,&sca[i].val);
            sca[i].xr=sca[i].xl+w-1;
            sca[i].yr=sca[i].yl+h+1;
            now[i*2-1]=scan(sca[i].xl,sca[i].yl,sca[i].yr,sca[i].val);
            now[i*2]=scan(sca[i].xr,sca[i].yl,sca[i].yr,-sca[i].val);
            lsh[++lh]=sca[i].yl,lsh[++lh]=sca[i].yr;
        }
        sort(lsh+1,lsh+lh+1);lh=unique(lsh+1,lsh+lh+1)-lsh-1;
        sort(now+1,now+2*n+1);
        xds.build(1,1,lh);
        fxt(i,1,2*n){
            ans=max(ans,xds.mx[1]);
            now[i].l=lower_bound(lsh+1,lsh+lh+1,now[i].l)-lsh;
            now[i].r=lower_bound(lsh+1,lsh+lh+1,now[i].r)-lsh;
            xds.ins(1,1,lh,now[i].l,now[i].r,now[i].val);
        }ans=max(ans,xds.mx[1]);
        printf("%lld\n",ans);
    }
}
2022/11/20 13:58
加载中...