POJ 2482 Stars in Your Window(线段树+扫描线)

非常不容易的一道题，把每个点向右上构造一个矩形，将问题转化为重合矩形那个亮度最大，注意LL，注意排序。
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <string>
  4 #include <algorithm>
  5 using namespace std;
  6 #define maxn 50100
  7 #define lson l,m,rt<<1
  8 #define rson m+1,r,rt<<1|1
  9 #define LL __int64
 10 struct node
 11 {
 12     LL lx,rx,y;
 13     LL s;
 14     node(){}
 15     node(LL a,LL b,LL c,LL d):lx(a),rx(b),y(c),s(d){}
 16     bool operator < (const node &S) const
 17     {
 18         if(y == S.y)
 19         return s > S.s;
 20         else
 21         return y < S.y;
 22     }
 23 }mat[maxn];
 24 LL que[2*maxn];
 25 LL tree[4*maxn];
 26 LL lz[4*maxn];
 27 void pushup(int rt)
 28 {
 29     tree[rt] = max(tree[rt<<1],tree[rt<<1|1]);
 30 }
 31 void pushdown(int rt)
 32 {
 33     if(lz[rt])
 34     {
 35         lz[rt<<1] += lz[rt];
 36         lz[rt<<1|1] += lz[rt];
 37         tree[rt<<1] += lz[rt];
 38         tree[rt<<1|1] += lz[rt];
 39         lz[rt] = 0;
 40     }
 41 }
 42 void update(int L,int R,int c,int l,int r,int rt)
 43 {
 44     int m;
 45     if(L <= l&&r <= R)
 46     {
 47         tree[rt] += c;
 48         lz[rt] += c;
 49         return ;
 50     }
 51     pushdown(rt);
 52     m = (l+r)>>1;
 53     if(L <= m)
 54     update(L,R,c,lson);
 55     if(R > m)
 56     update(L,R,c,rson);
 57     pushup(rt);
 58 }
 59 int bin(LL x,int n)
 60 {
 61     int str,mid,end;
 62     str = 0;
 63     end = n;
 64     while(str <= end)
 65     {
 66         mid = (str+end)/2;
 67         if(que[mid] == x)
 68         return mid;
 69         else if(que[mid] > x)
 70         end = mid - 1;
 71         else
 72         str = mid + 1;
 73     }
 74     return mid;
 75 }
 76 int main()
 77 {
 78     int n,num,k,i;
 79     LL a,b,c,h,w;
 80     while(scanf("%d%I64d%I64d",&n,&w,&h)!=EOF)
 81     {
 82         num = 0;
 83         w--;
 84         h--;
 85         for(i = 0;i < n;i ++)
 86         {
 87             scanf("%I64d%I64d%I64d",&a,&b,&c);
 88             mat[num] = node(a,a+w,b,c);
 89             que[num++] = a;
 90             mat[num] = node(a,a+w,b+h,-c);
 91             que[num++] = a+w;
 92         }
 93         k = 1;
 94         sort(que,que+num);
 95         sort(mat,mat+num);
 96         for(i = 1;i < num;i ++)
 97         {
 98             if(que[i] != que[i-1])
 99             que[k++] = que[i];
100         }
101         LL maxz = 0;
102         memset(tree,0,sizeof(tree));
103         memset(lz,0,sizeof(lz));
104         for(i = 0;i < num;i ++)
105         {
106             int l = bin(mat[i].lx,k-1);
107             int r = bin(mat[i].rx,k-1);
108             if(l <= r) update(l,r,mat[i].s,0,k-1,1);
109             maxz = max(maxz,tree[1]);
110         }
111         printf("%I64d
",maxz);
112     }
113     return 0;
114 }