hdoj-4419 Colourful Rectangle

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

考点

  • 扫描线

题解

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 50;
int n, ltot, ytot, dy[2 * maxn];
ll res[8];

struct node1 {
  int rgb_[4];  // 下标1~3，R、G、B的个数
  ll len_[8];   // 下标1~7，RGB的7种状态的长度
  // 000代表当前与父结点颜色相同的个数，默认当前区域全部相同
  // 001代表R、010代表G、011代表RG，以此类推
} tree[4 * 2 * maxn];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define rgb(x) tree[x].rgb_
#define len(x) tree[x].len_

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

void up(int rt, int l, int r) {
  memset(len(rt), 0, sizeof(len(rt)));
  int status = 0;
  for (int i = 1; i <= 3; ++i) {
    if (rgb(rt)[i]) status |= 1 << (i - 1);
  }
  if (l == r) {
    len(rt)[status] = dy[r + 1] - dy[l];
  } else {
    for (int i = 0; i <= 7; ++i)
      len(rt)[i | status] += len(lson)[i] + len(rson)[i];
  }
}

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

void build(int rt, int l, int r) {
  if (l == r) {
    len(rt)[0] = dy[r + 1] - dy[l];
    return;
  }
  int mid = (l + r) / 2;
  build(lson, l, mid), build(rson, mid + 1, r);
  len(rt)[0] = len(lson)[0] + len(rson)[0];
}

void work() {
  cin >> n;
  int bit, x1, x2, y1, y2;
  char ch;
  for (int i = 1; i <= n; ++i) {
    cin >> ch >> x1 >> y1 >> x2 >> y2;
    if (ch == 'R') {
      bit = 1;
    } else if (ch == 'G') {
      bit = 2;
    } else {
      bit = 3;
    }
    line[++ltot] = {x1, y1, y2, bit, 1}, line[++ltot] = {x2, y1, y2, bit, -1};
    dy[++ytot] = y1, dy[++ytot] = y2;
  }
  sort(dy + 1, dy + 1 + ytot);
  sort(line + 1, line + 1 + ltot);
  ytot = unique(dy + 1, dy + 1 + ytot) - dy - 1;
  build(1, 1, ytot - 1);
  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].bit_, line[i].flag_);
    for (int j = 1; j <= 7; ++j) {
      res[j] += 1ll * len(1)[j] * (line[i + 1].x_ - line[i].x_);
    }
  }
}

int main() {
  int t;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    ytot = ltot = 0;
    memset(tree, 0, sizeof(tree));
    memset(res, 0, sizeof(res));
    work();
    cout << "Case " << i << ":" << endl;
    cout << res[1] << endl << res[2] << endl << res[4] << endl;
    cout << res[3] << endl << res[5] << endl << res[6] << endl;
    cout << res[7] << endl;
  }
  return 0;
}

思路

矩形面积并的板子题，这不是难点。

本题最难的点，在于如何设计线段树；众所周知，扫描线不需要下放懒标记，只需要上传。

一共有7个状态，当然可以用7个变量...但是那样维护起来太变态了，可以用位运算。

B(高位) G R(低位)
0 0 0

如上所示，用三位就可以表达8种情况了：

  • R：001
  • G：010
  • B：100
  • RG：011
  • RB：101
  • GB：110
  • RGB：111

那么只要建立一个下标为0~7的长度数组，即可保存上述状态各自的长度。

假设当前有线段树如下，考虑子结点(1,2)与父结点(1,3)合并

显然，先要将父结点的长度数组归零，因为要和子结点的状态重新合并；而状态合并直接用或运算即可。

很显然能想到下列代码：

1
2
3
for(int i = 1; i <= 7; ++i){
    长度数组[当前状态 | i] += 左孩子的长度数组[i] + 右孩子的长度数组[i];
}

执行后父结点变成了下图的模样：

发现父结点原来还有一个B被清除了，该怎么办呢？将长度数组里的000状态用起来！

0状态代表当前与父结点保持一致的个数，默认为当前区间长度（个数）

只需要将上述代码改成：

1
2
3
for(int i = 0; i <= 7; ++i){
    长度数组[当前状态 | i] += 左孩子的长度数组[i] + 右孩子的长度数组[i];
}

多了一种情况，那就是

1
长度数组[当前状态] += 左孩子的长度数组[0] + 右孩子的长度数组[0];

以此来维护父结点的原状态个数。

最终的线段树长成这样：