BZOJ1218（线段树+扫描线）

1.扫描线扫描x轴，线段树维护y轴。

2.坐标+1，线段树是从1开始维护。然后让边长--，这样就能包含边上的点了。

3.为了保证点在正方形内：在x轴上利用差分的思想，在x出Add（val），在x+r（已经-1了）处Add（-val）；在y轴上利用线段树维护1～5001这个区间，在y～y+r上Add（val）。

题解博客大家都是口胡感觉难以讲清这个事情，这篇博客虽然没解释但代码逻辑不错，看懂的。

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <ctime>

 #include <cctype>

 #include <climits>

 #include <iostream>

 #include <iomanip>

 #include <algorithm>

 #include <string>

 #include <sstream>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <vector>

 #include <list>

 #include <fstream>

 #include <bitset>

 #define init(a, b) memset(a, b, sizeof(a))

 #define rep(i, a, b) for (int i = a; i <= b; i++)

 #define irep(i, a, b) for (int i = a; i >= b; i--)

 #define ls(p)    p << 1

 #define rs(p)    p << 1 | 1

 using namespace std;

 typedef double db;

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int, int> P;

 const int inf = 0x3f3f3f3f;

 const ll INF = 1e18;

 template <typename T> void read(T &x) {

     x = ;

     int s = , c = getchar();

     for (; !isdigit(c); c = getchar())

         if (c == '-')    s = -;

     for (; isdigit(c); c = getchar())

         x = x *  + c - ;

     x *= s;

 }

 template <typename T> void write(T x) {

     if (x < )    x = -x, putchar('-');

     if (x > )    write(x / );

     putchar(x %  + '');

 }

 template <typename T> void writeln(T x) {

     write(x);

     puts("");

 }

 const int maxn = 1e4 + , M = ;

 int n, r, cnt;

 struct Seg {

     int l, r, mx, tag;

 }t[(M + ) << ];

 struct node {

     int x, y1, y2, val;

 }c[maxn << ];

 void build(int l, int r, int p) {

     t[p].l = l, t[p].r = r;

     if (l == r) {

         t[p].mx = t[p].tag = ;

         return;

     }

     int mid = (l + r) >> ;

     build(l, mid, ls(p));

     build(mid + , r, rs(p));

 }

 void push_down(int p) {

     if (t[p].tag) {

         int tag = t[p].tag;

         t[ls(p)].mx += tag;

         t[rs(p)].mx += tag;

         t[ls(p)].tag += tag;

         t[rs(p)].tag += tag;

         t[p].tag = ;

     }

 }

 void Add(int l, int r, int p, int k) {

     if (l <= t[p].l && t[p].r <= r) {

         t[p].tag += k;

         t[p].mx += k;

         return;

     }

     push_down(p);

     int mid = (t[p].l + t[p].r) >> ;

     if (l <= mid)    Add(l, r, ls(p), k);

     if (mid < r)    Add(l, r, rs(p), k);

     t[p].mx = max(t[ls(p)].mx, t[rs(p)].mx);

 }

 int Query(int l, int r, int p) {

     if (l <= t[p].l && t[p].r <= r) {

         return t[p].mx;

     }

     push_down(p);

     int ret = ;

     int mid = (t[p].l + t[p].r) >> ;

     if (l <= mid)    ret = max(ret, Query(l, mid, ls(p)));

     if (mid < r)    ret = max(ret, Query(mid + , r, rs(p)));

     return ret;

 }

 bool cmp(node a, node b) {

     if (a.x != b.x)    return a.x < b.x;

     return a.val > b.val;

 }

 int solve() {

     int ans = ;

     build(, M, );

     rep(i, , n) {

         int x, y, z;

         read(x), read(y), read(z);

         c[++cnt] = {x + , y + , y + r, z};

         c[++cnt] = {x + r, y + , y + r, -z};

     }

     sort(c + , c +  + cnt, cmp);

     for (int i = , j, k; i <= cnt; i = j) {

         int tmp = c[i].x;

         for (j = i; j <= cnt && c[j].x == tmp; j++);

         for (k = i; k < j && c[k].val > ; k++) {

             Add(c[k].y1, c[k].y2, , c[k].val);

         }

         ans = max(ans, Query(, M, ));

         for (; k < j; k++) {

             Add(c[k].y1, c[k].y2, , c[k].val);

         }

     }

     return ans;

 }

 int main() {

     read(n), read(r);

     writeln(solve());

     return ;

 }

巴特西

BZOJ1218（线段树+扫描线）

最新文章

热门文章