poj2482--Stars in Your Window(掃描線)

poj2482--Stars in Your Window(掃描線)

鏈接題目大意：給出n個星星的坐標，每個星星有一個亮度，給出一個矩形的長和寬，問矩形能包括的星星的最大亮度和（不包括邊框）。

假設每個星星都是矩形的最左下點，那麼每一個星星都可以得到一個矩形，(x,y)->(x,y,x+w,y+h)，這個矩形的兩條高邊的值也就是星星的亮度k和-k，對於不同的矩形來說，如果高線出現重合部分，那麼也就是說這兩個星是可以出現在同一個矩形中的，掃描線求出可能出現的最大的亮度和。

注意：因為不包括邊框，所以掃描時應先掃描值為負的高線，並且僅對值為正的高線統計最大值。

#include 
#include 
#include 
using namespace std ;
#define LL __int64
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2,r,rt<<1|1
#define root 1,num_y,1
#define int_rt int l,int r,int rt
struct node{
    LL x , y1 , y2 ;
    LL k ;
}p[30000];
LL y[30000] ;
int cnt , num_y ;
struct node1{
    LL max1 , l , r , lazy ;
}cl[200000];
int cmp(node a,node b) {
    return a.x < b.x || ( a.x == b.x && a.k < 0 ) ;
}
void push_up(int rt) {
    cl[rt].max1 = max(cl[rt<<1].max1,cl[rt<<1|1].max1) + cl[rt].lazy;
}
void create(int_rt) {
    cl[rt].max1 = cl[rt].lazy = 0 ;
    cl[rt].l = y[l] , cl[rt].r = y[r] ;
    if( r - l == 1 ) {
        return ;
    }
    create(lson) ;
    create(rson) ;
    push_up(rt) ;
}
void update(LL ll,LL rr,LL k,int rt) {
    if( cl[rt].l >= ll && cl[rt].r <= rr ) {
        cl[rt].lazy += k ;
        cl[rt].max1 += k ;
        return ;
    }
    if( ll < cl[rt<<1].r )
        update(ll,min(rr,cl[rt<<1].r),k,rt<<1) ;
    if( rr > cl[rt<<1|1].l )
        update(max(cl[rt<<1|1].l,ll),rr,k,rt<<1|1) ;
    push_up(rt) ;
}
int main() {
    LL n , w , h , xx , yy , k , max1 ;
    int i , j ;
    while( scanf(%I64d %I64d %I64d, &n, &w, &h) != EOF ) {
        cnt = 0 , num_y = 1 ;
        max1 = 0 ;
        for(i = 1 ; i <= n ; i++) {
            scanf(%I64d %I64d %I64d, &xx, &yy, &k) ;
            p[cnt].x = xx ; p[cnt].y1 = yy ; p[cnt].y2 = yy+h ;
            p[cnt++].k = k ;
            p[cnt].x = xx+w ; p[cnt].y1 = yy ; p[cnt].y2 = yy+h ;
            p[cnt++].k = -k ;
            y[num_y++] = yy ;
            y[num_y++] = yy+h ;
        }
        sort(y+1,y+num_y) ;
        num_y = unique(y+1,y+num_y) - (y+1) ;
        sort(p,p+cnt,cmp) ;
        create(root) ;
        for(i = 0 ; i < cnt ; i++) {
            update(p[i].y1,p[i].y2,p[i].k,1) ;
            if( p[i].k  > 0 )
                max1 = max(max1,cl[1].max1) ;
        }
        printf(%I64d
, max1) ;
    }
    return 0 ;
}