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.x
  
   b.s;
}

int Max(int a,int b)
{
    if (a
   
    mid) 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;i
    
     40000) y=40000; updata(mark[i].y,y,1,mark[i].s); ans=Max(ans,data[1].x); } printf("%d\n",ans); } return 0; }