poj-2482-Stars in Your Window-线段树

线段树。

题意：平面上有许多点，每个点有一个权值。给定一个大小确定的矩形，边与x，y轴平行，平移这个矩形能圈住的点的权值之和最大是多少。

注意：矩形边上的不算，所以应该把矩形缩小一点。数据范围会超int，建议用long long

做法：

先把题目转化一下，用矩形的中心点来描述这个矩形的位置。并对每个点建立一个矩形中心点的活动范围，即矩形中心点在这个范围内即可覆盖到该点，建立方法就是以每个点为中心画一个与题中矩形大小相等的矩形。现在点变成了矩形，矩形变成了点。我们要求的是找一个位置来放这个点使得它在最多的矩形内部，即该点的矩形重叠层数最多。

这样我们就可以用线段树来解决了，用一条与y轴平行的扫描线，从左到右来扫描这个矩形重叠图。这条扫描线就是线段树中的整条线段区间，在一个时刻这个线段的不同位置被覆盖了不同层数的矩形，对每次扫描线产生变化后（扫入某一矩形或扫出某一矩形后）求现在正在扫的矩形在线段上覆盖的最大层数。

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define maxn 110000 #define LL long long struct list { LL l,r,x,val; } node[maxn*6]; struct liss { LL x; LL y1,y2; LL c,val; } line[maxn*2]; LL lines; LL yy[maxn]; LL a[maxn],b[maxn],c[maxn]; LL sk; LL n,W,H; LL maxx; int cmp(struct liss a,struct liss b) { if(a.x!=b.x)return a.x
      
       b.val; } LL search(LL x) { LL l=0; LL r=sk; LL mid=(l+r)/2; while(l
       
        x)r=mid; if(yy[mid]
        
         rr||r