線段樹典型例題--poj2482

【題意】

Assume the sky is a flat plane. All the stars lie on it with a location (x, y). for each star, there is a grade ranging from 1 to 100, representing its brightness, where 100 is the brightest and 1 is the weakest. The window is a rectangle whose edges are parallel to the x-axis or y-axis. Your task is to tell where I should put the window in order to maximize the sum of the brightness of the stars within the window. Note, the stars which are right on the edge of the window does not count. The window can be translated but rotation is not allowed.

There are at least 1 and at most 10000 stars in the sky. 1<=W，H<=1000000, 0<=x，y<2^31.

【題解】

首先是離散化+掃描線，但線段樹如何維護？

將星星拆成兩個，(x[i],y[i],light[i])和(x[i],y[i]+h,-light[i])，然後維護兩個量，sum和maxsum。sum是前綴和，maxsum是最大的前綴和

具體維護看代碼

【代碼】

[cpp] 
#include <iostream> 
#include <cstring> 
#include <string> 
#include <cstdio> 
#include <algorithm> 
using namespace std; 
 
const int N=10005; 
 
struct node 
{ 
    int x,y,idx1,idx2,c; 
}a[N]; 
 
int ss[N*10],ms[N*10]; 
long long g[N*3]; 
 
void ins(int i,int l,int r,int x,int cc) 
{ 
    if (l==r) 
    { 
        ss[i]+=cc; 
        ms[i]+=cc; 
        return; 
    } 
    int mid=(l+r)/2; 
    if (x<=mid) ins(i*2,l,mid,x,cc); 
    else ins(i*2+1,mid+1,r,x,cc); 
    ss[i]=ss[i*2]+ss[i*2+1]; 
    ms[i]=max(max(ms[i*2],ss[i*2]+ms[i*2+1]),ss[i*2]); 
} 
 
bool cmp(node a,node b) 
{ 
    return a.x<b.x || (a.x==b.x && a.y<b.y); 
} 
 
int main() 
{ 
    int tot,xl,xr,i,tmp,n,w,h,ans; 
 
    freopen("in2","r",stdin); 
    while (scanf("%d%d%d",&n,&w,&h)!=EOF) 
    { 
        memset(ss,0,sizeof(ss)); 
        memset(ms,0,sizeof(ms)); 
        tot=ans=0; 
        for (i=0;i<n;i++) 
        { 
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c); 
            g[tot++]=a[i].y; 
            g[tot++]=(long long)a[i].y+h; 
        } 
        sort(g,g+tot); 
        tot=unique(g,g+tot)-g; 
        sort(a,a+n,cmp); 
        for (i=0;i<n;i++) 
        { 
            a[i].idx1=lower_bound(g,g+tot,a[i].y)-g+1; 
            a[i].idx2=lower_bound(g,g+tot,(long long)a[i].y+h)-g+1; 
        } 
        xl=xr=0; 
        while (xr<n && a[xr].x-a[xl].x<w) 
        { 
            ins(1,1,tot,a[xr].idx1,a[xr].c); 
            ins(1,1,tot,a[xr].idx2,-a[xr].c); 
            xr++; 
        } 
        xr--; 
        while (xl<=xr) 
        { 
            ans=max(ans,ms[1]); 
            tmp=xl; 
            while (xl<=xr && a[xl].x==a[tmp].x) 
            { 
                ins(1,1,tot,a[xl].idx1,-a[xl].c); 
                ins(1,1,tot,a[xl].idx2,a[xl].c); 
                xl++; 
            } 
            while (xr+1<n && a[xr+1].x-a[xl].x<w) 
            { 
                xr++; 
                ins(1,1,tot,a[xr].idx1,a[xr].c); 
                ins(1,1,tot,a[xr].idx2,-a[xr].c); 
            } 
        }   www.2cto.com
        printf("%d\n",ans); 
    } 
}