POJ 2482 扫描线+离散化+线段树 (内容最浪漫的题目)

http://162.105.81.212/JudgeOnline/problem?id=2482

题目大意：

给定一个W*H的矩形，再给出一些在平面直角坐标系里的星星，每个星星有一个亮度，求用这个矩形去框住一些星星，使得框内的星星亮度之和最大。

HINT:

压在矩形的右边框或下边框的星星不算被框住。

其实一开始把w和h分别减1，然后按矩形处理就可以了。

另外要使用INT64

解题分析：

这个题目可以先把y坐标离散化。然后在Y轴建立线段树，再扫描X轴，动态维护一个关于x坐标的极大范围。然后用线段树维护最大值即可。注意，在Y轴上的插入的线段表示的是把这个范围内的点作为最高点，能够覆盖到星星i。

插曲：

这是GDOI之前老姜要求做的一题。当时看到晕掉了没做，在学校调了一周没调出来，老是WA。最后理清思路，在家重打了一遍，一次编译成功，一次AC。

code：

#include #include #include #include #define L(x) (x)<<1
#define R(x) ((x)<<1)|1
#define MAXN 111111
using namespace std;
struct startype{__int64 x,y,w;}a[MAXN];
struct treetype{__int64 l,r,max,sum;}tr[MAXN*20];
__int64 n,xlen,ylen,yl[MAXN],m,tl[MAXN],toy[MAXN];

void DelSame(){
    m=0;
    for (__int64 i=1;i<=n;i++)
      if (m==0 || tl[m]!=yl[i])
        tl[++m]=yl[i];
    for (__int64 i=1;i<=n;i++) yl[i]=0;
    for (__int64 i=1;i<=m;i++) yl[i]=tl[i];
}

__int64 Find(__int64 k){
    __int64 l=1,r=m,mid;
    while (l        mid=l+r>>1;
        if (yl[mid]                  else r=mid;
    }
    return l;
}

void LiSan(){
    for (__int64 i=1;i<=n;i++)
      yl[i]=a[i].y;
    sort(&yl[1],&yl[n+1]);
    DelSame();
    for (__int64 i=1;i<=n;i++)
      a[i].y=Find(a[i].y);
}

void Build(__int64 p,__int64 l,__int64 r){
    tr[p].l=l; tr[p].r=r; tr[p].max=0; tr[p].sum=0;
    if (l        __int64 mid=l+r>>1;
        Build(L(p),l,mid);
        Build(R(p),mid+1,r);
    }
}

bool cmp(startype t1,startype t2){
    if (t1.x    return false;
}

void Toy(){
    __int64 i,j=0;
    for (i=1;i<=m;i++){
        while (j        toy[i]=j;
    }
}

void ins(__int64 p,__int64 l,__int64 r,__int64 w){
    if (r    if (l<=tr[p].l && tr[p].r<=r){
        tr[p].sum+=w;
        tr[p].max+=w;
        return;
    }
    if (tr[p].sum!=0){
        ins(L(p),0,m,tr[p].sum);
        ins(R(p),0,m,tr[p].sum);
        tr[p].sum=0;
    }
    ins(L(p),l,r,w);
    ins(R(p),l,r,w);
    tr[p].max=max(tr[L(p)].max,tr[R(p)].max);
}

void Work(){
    sort(&a[1],&a[n+1],cmp);
    __int64 i,j=0,ans=0;
    for (i=1;i<=n;i++){
        while (j            j++;
            ins(1,a[j].y,toy[a[j].y],a[j].w);
        }
        ans=max(ans,tr[1].max);
        ins(1,a[i].y,toy[a[i].y],-a[i].w);
    }
    cout << ans << endl;
}

int main(){
    while (cin >> n >> xlen >> ylen){
        xlen–; ylen–;
        for (__int64 i=1;i<=n;i++)
          scanf("%I64d %I64d %I64d",&a[i].x,&a[i].y,&a[i].w);
        LiSan();
        Build(1,1,m);
        Toy();
        Work();
    }
    return 0;
}