P1884. Overplanting S

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 809 阅读时长 ≈ 3 分钟

考点

  • 离散化
  • 差分
  • 扫描线

题解

见思路

思路

差分

以样例0 5 4 1为例，先要把它们转换成常规数组下的坐标（这里都是点啊！不是格子！）

由于1e8远超数组下标能表达的范围，显然需要先离散化处理，然后根据样例作图：

由于是不规则的矩形，考虑P1496的做法：

令diff[i][j]表示i行j列为左上角，i + 1行j + 1列为右下角的单位矩形，即下图的绿色单位矩形；

不管重复染色多少次，只要染色的单位矩形就只统计一次；

这样统计全图的绿色单位矩形就能得到不规则矩形面积。

但显然，每个大矩形最多有接近4000 * 4000个单位矩形，最多1000个大矩形，是绝对会TLE的。

所以采用差分，每行进行批量修改即可，如图操作即可修改绿色一行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 50;
int n, btop, b[4 * maxn], ctop, c[4 * maxn];
int diff[4 * maxn][4 * maxn];
unordered_map<int, int> mp;

struct node {
  int x1_, y2_, x2_, y1_;
} a[maxn];

int main() {
  int x1, y1, x2, y2;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    // 注意换了位置
    cin >> a[i].x1_ >> a[i].y2_ >> a[i].x2_ >> a[i].y1_;
    b[++btop] = a[i].x1_, b[++btop] = a[i].y2_;
    b[++btop] = a[i].x2_, b[++btop] = a[i].y1_;
  }
  // 离散化
  sort(b + 1, b + 1 + btop);
  for (int i = 1; i <= btop; ++i) {
    if (i == 1 || b[i] != b[i - 1]) {
      c[++ctop] = b[i];
      mp[b[i]] = ctop;
    }
  }
  // 按行差分
  for (int i = 1; i <= n; ++i) {
    int x1 = mp[a[i].x1_], x2 = mp[a[i].x2_], y1 = mp[a[i].y1_],
        y2 = mp[a[i].y2_];
    for (int row = x1; row < x2; ++row) {
      ++diff[row][y1], --diff[row][y2];
    }
  }
  // 按行前缀和
  for (int i = 1; i < ctop; ++i) {
    for (int j = 1; j < ctop; ++j) {
      diff[i][j] += diff[i][j - 1];
    }
  }
  ll ans = 0;
  for (int i = 1; i < ctop; ++i) {
    for (int j = 1; j < ctop; ++j) {
      if (diff[i][j]) {
        ans += 1ll * (c[i + 1] - c[i]) * (c[j + 1] - c[j]);
      }
    }
  }
  cout << ans;
  return 0;
}

扫描线

本题的正解，直接套扫描线求面积并的板子即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 50;
int n, ytot, ltot, dy[2 * maxn];

struct node1 {
  int x_, y1_, y2_, flag_;
  bool operator<(node1 &x) { return x_ < x.x_; }
} line[2 * maxn];

struct node2 {
  int status_;
  ll sum_;
} seg[4 * 2 * maxn];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define stat(x) seg[x].status_
#define sum(x) seg[x].sum_

void up(int rt, int l, int r) {
  sum(rt) = stat(rt) ? dy[r + 1] - dy[l] : (l == r ? 0 : sum(lson) + sum(rson));
}

void update(int rt, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) {
    stat(rt) += v, up(rt, l, r);
    return;
  }
  int mid = (l + r) / 2;
  if (L <= mid) update(lson, l, mid, L, R, v);
  if (R > mid) update(rson, mid + 1, r, L, R, v);
  up(rt, l, r);
}

int main() {
  cin >> n;
  int x1, y1, x2, y2;
  for (int i = 1; i <= n; ++i) {
    // (x1, y2)为矩形左下角，(x2, y1)为矩形右上角
    cin >> x1 >> y2 >> x2 >> y1;
    dy[++ytot] = y1, dy[++ytot] = y2;
    line[++ltot] = {x1, y1, y2, 1}, line[++ltot] = {x2, y1, y2, -1};
  }
  sort(dy + 1, dy + 1 + ytot), sort(line + 1, line + 1 + ltot);
  ytot = unique(dy + 1, dy + 1 + ytot) - 1 - dy;
  ll ans = 0;
  for (int i = 1; i < ltot; ++i) {
    y1 = lower_bound(dy + 1, dy + 1 + ytot, line[i].y1_) - dy;
    y2 = lower_bound(dy + 1, dy + 1 + ytot, line[i].y2_) - dy;
    update(1, 1, ytot - 1, y1, y2 - 1, line[i].flag_);
    ans += sum(1) * (line[i + 1].x_ - line[i].x_);
  }
  cout << ans;
  return 0;
}