线段树+扫描线+离散化的好题

limi_sanhua · 2019-04-23 16:58:08 · 个人记录

洛谷 P1502 窗口的星星

#pragma GCC optimize("Ofast")
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define u int
#define ri register int
#define NN 500005
u t[NN],a[NN];
void in(u &x) {
    x=0;
    u f(1);
    char s=getchar();
    while(s<'0'||s>'9') {
        if(s=='-') {
            f=-1;
        }
        s=getchar();
    }
    while(s>='0'&&s<='9') {
        x=x*10+s-'0';
        s=getchar();
    }
    x*=f;
}
void out(u x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9) {
        out(x/10);
    }
    putchar(x%10+'0');
}
struct reg{
    u x,y,xx,z;
    reg(){}
    reg(u x1,u yy1,u xx1,u z1){
        x=x1;
        y=yy1;
        xx=xx1;
        z=z1;
    }
}line[NN];
bool cmp(reg a,reg b){
    if(a.y==b.y)return a.z>b.z;
    return a.y<b.y;
}
u sum[NN],add[NN];
void pushdown(u rt,u l,u r)
{
    if(!add[rt])
    {
        return;
    }
    u xrt=rt<<1;
    u mid=(r+l)>>1;
    sum[xrt]+=add[rt];
    sum[xrt|1]+=add[rt];
    add[xrt]+=add[rt];
    add[xrt|1]+=add[rt];
    add[rt]=0;
}
void update(u rt,u l,u r,u x,u y,u v)
{
    if(x<=l&&y>=r)
    {
        sum[rt]+=v;
        add[rt]+=v;
        return;
    }
    pushdown(rt,l,r);
    u mid=(l+r)>>1;
    if(x<=mid)
    {
        update(rt<<1,l,mid,x,y,v);
    }
    if(mid<y)
    {
        update(rt<<1|1,mid+1,r,x,y,v);
    }
    pushdown(rt<<1,l,mid);
    pushdown(rt<<1|1,mid+1,r);
    sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
u xxx[NN];
int main() {
    //freopen("x.txt","r",stdin);
    u T;
    in(T);
    while(T--){
        u a,b,c;
        in(a);//a颗星星 
        in(b);//wei
        in(c);//hi
        u x,y,z;
        for(ri i=1;i<=a;++i){
            in(y);//x
            in(x);//y
            in(z);//亮度 
            line[i]=reg(x,y,x+c-1,z);
            line[i+a]=reg(x,y+b-1,x+c-1,-z);
            xxx[i]=x;
            xxx[i+a]=x+c-1;
        }
        u ss=a*2;
        sort(xxx+1,xxx+ss+1);
        u m=unique(xxx+1,xxx+ss+1)-xxx-1;
        sort(line+1,line+ss+1,cmp);
        u ans=0;
        for(ri i=1;i<=ss;++i){
            u q=lower_bound(xxx+1,xxx+m+1,line[i].x)-xxx;
            u w=lower_bound(xxx+1,xxx+m+1,line[i].xx)-xxx;
            update(1,1,m,q,w,line[i].z);
            ans=max(ans,sum[1]);
        }
        out(ans);
        putchar('\n');
        memset(sum,0,sizeof(sum));
        memset(add,0,sizeof(add));
    }
}