poj2482Stars in Your Window(线段树+离散化+扫描线）

类似于上一篇这题转化的比较巧妙将一个点转化为一个矩形(x,y, x+w,y+h),扫描线入值为正出值为负

也就是一根线过去每进入一个矩形都更新线上的总值取一个最大值

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stdlib.h>
  6 using namespace std;
  7 #define N 20010
  8 #define LL long long
  9 struct node
 10 {
 11     LL lx,rx,y,s;
 12     node(){}
 13     node(LL a,LL b,LL c,LL d):lx(a),rx(b),y(c),s(d){}
 14     bool operator <(const node &S)const
 15     {
 16         if(y==S.y)
 17         return s>S.s;
 18         return y<S.y;
 19     }
 20 }te[N];
 21 int sum[N<<2],cov[N<<2],que[N];
 22 int bin(LL x,int n)
 23 {
 24     int s=0,e = n,m;
 25     while(s<=e)
 26     {
 27         m = (s+e)/2;
 28         if(que[m]==x)
 29         return m;
 30         else if(que[m]>x)
 31         e = m-1;
 32         else
 33         s = m+1;
 34     }
 35     return m;
 36 }
 37 void pushdown(int w)
 38 {
 39     if(cov[w])
 40     {
 41         cov[w<<1] += cov[w];
 42         cov[w<<1|1] += cov[w];
 43         sum[w<<1] += cov[w];
 44         sum[w<<1|1] += cov[w];
 45         cov[w] = 0;
 46     }
 47 }
 48 void pushup(int w)
 49 {
 50     sum[w] = max(sum[w<<1],sum[w<<1|1]);
 51 }
 52 void update(int a,int b,int d,int l,int r,int w)
 53 {
 54     if(a<=l&&b>=r)
 55     {
 56         sum[w]+=d;
 57         cov[w]+=d;
 58         return ;
 59     }
 60     pushdown(w);
 61     int m = (l+r)>>1;
 62     if(a<=m)
 63     update(a,b,d,l,m,w<<1);
 64     if(b>m)
 65     update(a,b,d,m+1,r,w<<1|1);
 66     pushup(w);
 67 }
 68 int main()
 69 {
 70     int i,k,n;
 71     LL w,h,x,y,v;
 72     while(cin>>n>>w>>h)
 73     {
 74         int num = 0;
 75         w--;h--;
 76         for(i = 1; i <= n ;i++)
 77         {
 78             cin>>x>>y>>v;
 79             que[num] = x;
 80             te[num++] = node(x,x+w,y,v);
 81             que[num] = x+w;
 82             te[num++] = node(x,x+w,y+h,-v);
 83         }
 84         sort(que,que+num);
 85         sort(te,te+num);
 86         k = 1;
 87         for(i = 1 ; i < num ; i++)
 88         {
 89             if(que[i]!=que[i-1])
 90             que[k++] = que[i];
 91         }
 92         int maxz = 0;
 93         for(i = 0 ; i < num ; i++)
 94         {
 95             int l = bin(te[i].lx,k-1);
 96             int r = bin(te[i].rx,k-1);
 97             update(l,r,te[i].s,0,k-1,1);
 98             maxz = max(maxz,sum[1]);
 99         }
100         cout<<maxz<<endl;
101     }
102     return 0;
103 }

View Code