POJ 2482 Stars in Your Window (线段树区间合并+扫描线)

　　这题开始一直被矩形框束缚了，想法一直都是枚举线，但是这样枚举都需要O（n^2）。。。但是看了别人的思路，感觉这题思想真心很好（PS：开头好浪漫的描述啊，可惜并没有什么用）
　　题意就是在平面上给你一些星星，一定是整数点，每颗星星有一个亮度，然后给你一个固定大小只能移动不能旋转的矩形框，问你任意移动矩形框最多可以将星星的最大的亮度装进框内，注意框边上的星星不计算

　　以前做过有个类似的题，但是数据范围小又很水，因为可以枚举每个点作为四个角分别统计就过了。可是这样是错的，因为可能有情况是四个点分别限制矩形框的四边，这样的情况就不能处理。
　　很多二维题都是二维变一维，先枚举一维，接着用一些数据结构高效的维护另一维。
　　这个题所使用的方法其实也是排序一维，然后模拟矩形框来维护两条扫描线在这一维上移动，接着处理第二维在限制长度内的最大值。换句话就是用两个指针维护x轴，接着用添加点，删除点的方式维护y轴。但是在限制长度下求最大区间和不太好做，我们可以模拟树状数组的区间更新，在每个点的（y轴+限制长度）的位置添加一个负的亮度，这样我们就转化为了求最大区间和（没有了限制长度），直接套一个线段树区间合并。注意这儿数据范围很大需要离散化，但是要搞清楚我们只需要离散化后的每个y值对应的是树上的哪个位置（其实就是第几大），使用map就可以解决

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define eps 1E-8

/*注意可能会有输出-0.000*/

#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型

#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化

#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0

#define mul(a,b) (a<<b)

#define dir(a,b) (a>>b)

typedef long long ll;

typedef unsigned long long ull;

const int Inf=<<;

const double Pi=acos(-1.0);

const int Max=;

map<ll,int> mp;//离散化成1到coun

struct node

{

    ll bri;

    ll xx1,yy1;

} poi[Max];

struct nide

{

    ll lmax,rmax,mmax,sum;

    void init(ll num)

    {

        sum=lmax=rmax=mmax=num;

    }

} segtr[Max*<<]; //再多开一倍空间

bool cmp1(struct node p1,struct node p2)

{

    return p1.xx1<p2.xx1;

}

ll nmax(ll a,ll b)

{

    return a>b?a:b;

}

void Upnow(int now,int next)

{

    segtr[now].sum=segtr[next].sum+segtr[next|].sum;

    segtr[now].lmax=nmax(segtr[next].lmax,segtr[next].sum+segtr[next|].lmax);

    segtr[now].rmax=nmax(segtr[next|].rmax,segtr[next|].sum+segtr[next].rmax);

    segtr[now].mmax=nmax(nmax(segtr[next].mmax,segtr[next|].mmax),segtr[next].rmax+segtr[next|].lmax);

    return;

}

void Create(int sta,int enn,int now)

{

    if(sta==enn)

    {

        segtr[now].init(0ll);

        return;

    }

    int mid=dir(sta+enn,);

    int next=mul(now,);

    Create(sta,mid,next);

    Create(mid+,enn,next|);

    Upnow(now,next);

    return;

}

void Update(int sta,int enn,int now,int x,ll y)

{

    if(sta==enn&&sta==x)

    {

        segtr[now].sum+=y;

        segtr[now].lmax+=y;

        segtr[now].rmax+=y;

        segtr[now].mmax+=y;

        return;

    }

    int mid=dir(sta+enn,);

    int next=mul(now,);

    if(mid>=x)

        Update(sta,mid,next,x,y);

    else

        Update(mid+,enn,next|,x,y);

    Upnow(now,next);

    return;

}

int main()

{

    ll n,w,h;

    while(~scanf("%lld %lld %lld",&n,&w,&h))

    {

        for(int i=; i<n; i++)

            scanf("%lld %lld %lld",&poi[i].xx1,&poi[i].yy1,&poi[i].bri);

        mp.clear();

        for(int i=; i<n; i++)//建树前离散化y轴

        {

            mp[poi[i].yy1]=;

            mp[poi[i].yy1+h]=;

        }

        int coun=;

        map<ll,int>::iterator it;

        for(it=mp.begin(); it!=mp.end(); ++it)

            it->second=coun++;

        coun--;

        Create(,coun,);

        int j=;//双指针作为扫描线

        ll manx=;

        sort(poi,poi+n,cmp1);

        for(int i=; i<n; i++) //关键：模拟树状数组的区间更新，后面对应位置加一个负的亮度，则就求最大区间和

        {

            Update(,coun,,mp[poi[i].yy1],poi[i].bri);//加点

            Update(,coun,,mp[poi[i].yy1+h],-poi[i].bri);//枚举的点

            while(i!=j&&poi[i].xx1-poi[j].xx1>=w)

            {

                Update(,coun,,mp[poi[j].yy1],-poi[j].bri);//删点

                Update(,coun,,mp[poi[j].yy1+h],poi[j].bri);

                j++;

            }

            manx=nmax(manx,segtr[].mmax);

        }

        printf("%lld\n",manx);

    }

    return ;

}

巴特西

POJ 2482 Stars in Your Window (线段树区间合并+扫描线)

最新文章

热门文章