HDU 5091 線段樹掃描線

HDU 5091 線段樹掃描線

給出N個點，和一個w*h的矩形

給出N個點的坐標，求該矩形最多可以覆蓋多少個點

對每個點point（x，y）右邊生成對應的點（x+w，y）值為-1；

縱向建立線段樹，從左到右掃描線掃一遍，遇到點則用該點的權值更新區間（y，y+h）

#include "stdio.h"
#include "string.h"
#include "algorithm"
using namespace std;

struct Mark
{
    int x,y,s;
}mark[30010];

struct node
{
    int l,r,x,lazy;
}data[200010];

bool cmp(Mark a, Mark b)
{
    if (a.x!=b.x)
    return a.xb.s;
}

int Max(int a,int b)
{
    if (amid) updata(l,r,k*2+1,op);
    else
    {
        updata(l,mid,k*2,op);
        updata(mid+1,r,k*2+1,op);
    }

    data[k].x=Max(data[k*2].x,data[k*2+1].x);
}
int main()
{
    int n,w,h,i,x,y,ans;
    while (scanf("%d",&n)!=EOF)
    {
        if (n<0) break;
        scanf("%d%d",&w,&h);
        for (i=0;i40000) y=40000;
            updata(mark[i].y,y,1,mark[i].s);
            ans=Max(ans,data[1].x);
        }
        printf("%d\n",ans);

    }
    return 0;
}