算法记录-2-（线段树-扫描线）

https://ncc79601.blog.luogu.org/scan-line
题目链接：https://vjudge.net/problem/POJ-1151
有时候一篇好的题解真的救人命，扫描线的原理一看就会，但代码实现着实费了老大功夫。上上下下找了不少题解，要么晦涩难懂，要么码风实在劝退。

• 算法描述：
  扫描线通常用来求叠加矩形的总面积，顾名思义，即对复合后的复杂图形从下至上或从左至右进行扫描，将图形拆分成多个小块，方便求取。小块的面积则是相邻两条扫描线的距离差乘以小块的另一条边长，而线段树则用来维护扫描线截取的线段长度。详情不再赘述，如果还有疑惑，请参照上述题解。

  #include <stdio.h>
  #include <iostream>
  #include <algorithm>
  #define lson (x << 1)
  #define rson (x << 1 | 1)
  using namespace std;
  const int MAXN = 1e6 + 10;
  typedef long long ll;
  int n, cnt = 0;
  ll x1, y1, x2, y2, X[MAXN << 1];
  struct ScanLine {
    ll l, r, h;
    int mark;
  //  mark用于保存权值 (1 / -1)
    bool operator < (const ScanLine &rhs) const {
        return h < rhs.h;
    }
  } line[MAXN << 1];
  struct SegTree {
    int l, r, sum;
    ll len;
  //  sum: 被完全覆盖的次数；
  //  len: 区间内被截的长度。
  } tree[MAXN << 2];
  void build_tree(int x, int l, int r) {
  //  我觉得最不容易写错的一种建树方法
    tree[x].l = l, tree[x].r = r;
    tree[x].len = 0;
    tree[x].sum = 0;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build_tree(lson, l, mid);
    build_tree(rson, mid + 1, r);
    return;
  }
  void pushup(int x) {
    int l = tree[x].l, r = tree[x].r;
    if(tree[x].sum /* 也就是说被覆盖过 */ )
        tree[x].len = X[r + 1] - X[l];
  //      更新长度        
    else
        tree[x].len = tree[lson].len + tree[rson].len;
  //      合并儿子信息
  }
  void edit_tree(int x, ll L, ll R, int c) {
    int l = tree[x].l, r = tree[x].r;
  //  注意，l、r和L、R的意义完全不同
  //  l、r表示这个节点管辖的下标范围
  //  而L、R则表示需要修改的真实区间
    if(X[r + 1] <= L || R <= X[l])
        return;
  //  这里加等号的原因：
  //  假设现在考虑 [2,5], [5,8] 两条线段，要修改 [1,5] 区间的sum
  //  很明显，虽然5在这个区间内，[5,8] 却并不是我们希望修改的线段
  //  所以总结一下，就加上了等号
    if(L <= X[l] && X[r + 1] <= R) {
        tree[x].sum += c;
        pushup(x);
        return;
    }
    edit_tree(lson, L, R, c);
    edit_tree(rson, L, R, c);
    pushup(x);
  }
  int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
        X[2 * i - 1] = x1, X[2 * i] = x2;
        line[2 * i - 1] = (ScanLine) {x1, x2, y1, 1};
        line[2 * i] = (ScanLine) {x1, x2, y2, -1};
  //      一条线段含两个端点，一个矩形的上下边都需要扫描线扫过
    }
    n <<= 1;
  //  直接把 n <<= 1 方便操作
    sort(line + 1, line + n + 1);
    sort(X + 1, X + n + 1);
    int tot = unique(X + 1, X + n + 1) - X - 1;
  //  去重最简单的方法：使用unique！（在<algorithm>库中）
    build_tree(1, 1, tot - 1);
  //  为什么是 tot - 1 ：
  //  因为右端点的对应关系已经被篡改了嘛…
  //  [1, tot - 1]描述的就是[X[1], X[tot]]
    ll ans = 0;
    for(int i = 1; i < n /* 最后一条边是不用管的 */ ; i++) {
        edit_tree(1, line[i].l, line[i].r, line[i].mark);
  //      先把扫描线信息导入线段树
        ans += tree[1].len * (line[i + 1].h - line[i].h);
  //      然后统计面积
    }
    printf("%lli", ans);
    return 0;
  }

  下面同样给出一道扫描线+线段树的例题，思路与上题如出一辙，个人觉得对星星的处理比较巧妙，本来是用方框去框住更多的星星，现在根据星星的坐标确定方框右端点所能存在的范围，题目一下子就从抽象变为具体了，妙！
  题目链接：https://vjudge.net/problem/POJ-2482#author=PMYCQACF

  #include <cstdio>
  #include <iostream>
  #include <algorithm>
  using namespace std;
  const int N = 10006;
  int n;
  struct P {
    unsigned int x, y, z;
    int c;
    bool operator < (const P w) const {
        return x < w.x || (x == w.x && c < w.c);
    }
  } a[N<<1];
  unsigned int w, h, b[N<<1];
  struct T {//ans保存最大值 
    int l, r, ans, add;
  } t[N<<3];
  void build(int p, int l, int r) {
    t[p].l = l;
    t[p].r = r;
    t[p].ans = t[p].add = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
  }
  void spread(int p) {
    t[p<<1].add += t[p].add;
    t[p<<1].ans += t[p].add;
    t[p<<1|1].add += t[p].add;
    t[p<<1|1].ans += t[p].add;
    t[p].add = 0;
  }
  void change(int p, int l, int r, int c) {
    if (l <= t[p].l && r >= t[p].r) {
        t[p].add += c;
        t[p].ans += c;
        return;
    }
    if (t[p].add) spread(p);
    int mid = (t[p].l + t[p].r) >> 1;
    if (l <= mid) change(p<<1, l, r, c);
    if (r > mid) change(p<<1|1, l, r, c);
    t[p].ans = max(t[p<<1].ans, t[p<<1|1].ans);
  }
  void Stars_in_Your_Window() {
    for (int i = 1; i <= n; i++) {
        int k = i << 1;
        scanf("%u %u %d", &a[k-1].x, &a[k-1].y, &a[k-1].c);
        a[k].x = a[k-1].x + w;//建立如(x,y,y+h-1,c) and (x+w,y,y+h-1,c) 的四元组，之所以-1是为了应对星星在边界的情况 
        b[k-1] = a[k].y = a[k-1].y;
        b[k] = a[k].z = a[k-1].z = a[k].y + h - 1;
        a[k].c = -a[k-1].c;
    }
    n <<= 1;
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; i++) {
        a[i].y = lower_bound(b + 1, b + m + 1, a[i].y) - b;//离散化的处理 
        a[i].z = lower_bound(b + 1, b + m + 1, a[i].z) - b;
    }
    sort(a + 1, a + n + 1);
    build(1, 1, m);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        change(1, a[i].y, a[i].z, a[i].c);
        ans = max(ans, t[1].ans);
    }
    cout << ans << endl;
  }
  int main() {
    while (cin >> n >> w >> h) Stars_in_Your_Window();
    return 0;
  }