POJ 2482 Stars in Your Window 线段树

　　如果按一般的思路来想，去求窗户能框住的星星，就很难想出来。

　　如果换一个思路，找出每颗星星能被哪些窗户框住，这题就变得非常简单了。

　　不妨以每个窗户的中心代表每个窗户，那么每颗星星所对应的窗户的范围即以其为中心的、W*H的矩形。把这些矩形的左边和右边，分别加上和减去其价值。而统计这些边只需要开一个线段树统计即可，用每次加边后得到的最大值更新答案。

　　需要注意的是，计算这些边上两点的坐标时可能出现0.5的情况，为了避免，把原坐标*2即可。而且坐标过大，需要离散化。

　　一开始打的时候，竟然，错了样例。仔细看了之后才发现窗户的长度为框住的点数+1，TAT

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <iostream>

 #include <map>

 using namespace std;

 #define ls (rt<<1)

 #define rs ((rt<<1)+1)

 typedef long long LL;

 const int maxn = ;

 int n, m, W, H;

 struct Node

 {

     LL x, y1, y2, v;

     Node (LL x = , LL y1 = , LL y2 = , int v = ):

         x(x), y1(y1), y2(y2), v(v) {}

     bool operator < (const Node &AI) const

     {

         if (x == AI.x)

             return v < AI.v;

         return x < AI.x;

     }

 }line[maxn*];

 LL t[maxn];

 struct Tree

 {

     LL mv[maxn*], delta[maxn*];

     void Build(int rt, int l, int r)

     {

         delta[rt] = mv[rt] = ;

         if (l == r)

             return ;

         int mid = (l+r)>>;

         Build(ls, l, mid);

         Build(rs, mid+, r);

     }

     void PushUp(int rt)

     {

         mv[rt] = max(mv[ls], mv[rs]);

     }

     void PushDown(int rt)

     {

         mv[ls] += delta[rt], mv[rs] += delta[rt];

         delta[ls] += delta[rt], delta[rs] += delta[rt];

         delta[rt] = ;

     }

     void Update(int rt, int l, int r, int L, int R, int k)

     {

         if (L <= l && r <= R)

         {

             mv[rt] += k;

             delta[rt] += k;

             return ;

         }

         if (delta[rt] != )

             PushDown(rt);

         int mid = (l+r)>>;

         if (L <= mid)

             Update(ls, l, mid, L, R, k);

         if (R > mid)

             Update(rs, mid+, r, L, R, k);

         PushUp(rt);

     }

 }T;

 map <LL, int> num_y;

 int main()

 {

     while (~scanf("%d %d %d", &n, &W, &H))

     {

         W ++, H ++;

         m = ;

         int Tcnt = ;

         for (int i = ; i <= n; ++i)

         {

             LL x, y, v;

             scanf("%lld %lld %lld", &x, &y, &v);

             line[++m] = Node(x*-(W-)+, y*-(H-)+, y*+(H-)-, v);

             line[++m] = Node(x*+(W-), y*-(H-)+, y*+(H-)-, -v);

             t[++Tcnt] = y*-(H-)+, t[++Tcnt] = y*+(H-)-;

         }

         sort(t+, t+Tcnt+);

         int las_cnt = Tcnt;

         Tcnt = ;

         for (int i = ; i <= las_cnt; ++i)

             if (t[i] != t[i-] || i == )

             {

                 t[++Tcnt] = t[i];

                 num_y[t[i]] = Tcnt;

             }

         sort(line+, line+m+);

         T.Build(, , Tcnt);

         LL ans = ;

         for (int i = ; i <= m; ++i)

         {

             T.Update(, , Tcnt, num_y[line[i].y1], num_y[line[i].y2], line[i].v);

             ans = max(ans, T.mv[]);

         }

         printf("%lld\n", ans);

     }

     return ;

 }

巴特西

POJ 2482 Stars in Your Window 线段树

最新文章

热门文章