题解：P15482 [CERC2012] Jewel heist

· · 题解

Solution

好题。

第一步转化是很显然的，既然不能选全部的 k 种颜色，那么考虑屏蔽掉一种颜色 c。

那么我们固定缺少一个颜色 c 之后，问题变成了什么呢？

当前情况下，颜色 c 的所有宝石全部都不能碰，它们像一根根钉子一样插在 x 轴上面。

对于某一个高度 H，所有高度 \le H 的颜色为 c 的宝石把 x 轴切成了若干段。

[0, x_1], [x_1, x_2], [x_2, x_3], \cdots, [x_\text{tot}, m + 1]

假如两个相邻的颜色为 c 的宝石的 x 坐标为 l, r，那么举行的左右边界只能取在：l < L \le R < r。

也就是说，对于一个固定的颜色 c 和高度 H，那么答案的候选就是在相邻两个 c 色障碍之间高度 \le H 的宝石数量。

高度 H 从小到大增加时：

那么，考虑扫描线。

把所有宝石先按 y 排序。

维护一个树状数组表示当前已经加入扫描线的宝石，按 x 坐标的个数。

维护一个障碍物集合 set<int> pos[kMaxN] 表示每种颜色已经出现的 x 坐标。

因为 x 坐标最大可以达到 10^9，所以先需要离散化。

假设当前扫描到一个宝石 (x, y, c)，我们钦定最终缺少的就是颜色 c。

在颜色 c 的障碍物集合中找到它的前驱 l 和后继 r，那么 (l, r) 就是当前可选的 x 坐标区间（注意不能选位置 l, r，会碰到障碍）。

由于此时树状数组内只有高度比 y 小的宝石，所以：Query(r - 1) - Query(l) 就是高度低于当前层，x \in (l, r) 的宝石数量。于是，更新答案。

讲一个重点，为什么 y 相同的点要一起处理？

假设当前高度 y 有多个宝石。

如果我们一个一个处理：

但实际我们可以把矩形高度取得比当前 y 稍微小一点，这样当前这一层的所有宝石都还没进入矩形，它们都不应该作为障碍。

所以，对于同一层 y，我们先用旧的 set 和树状数组用来更新答案，再把这一层的所有点插进去。

注意最后还要扫一遍，因为扫完宝石之后树状数组内已经包含所有宝石，此时可以看为 H 是无穷大的。

对于每种颜色 c，它所有的 x 坐标都已经是障碍，这些障碍把 x 轴切成若干段。那么每一段内部都没有颜色 c 的宝石，所以整段里的所有宝石都可以抓。

代码实现有一个细节：在每个颜色的障碍集合里加入 0 和 m + 1 作为两个哨兵，以防越界。

Code

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 2e5 + 10;

int n, m, k, tr[kMaxN], b[kMaxN], mx;
set<int> pos[kMaxN];

struct Node {
  int x, y, c;
  bool operator< (const Node &b) const {
    return y < b.y;
  }
} a[kMaxN];

int lowbit(int x) {
  return (x & (-x));
}

void Modify(int x, int k) {
  for (; x <= m; tr[x] += k, x += lowbit(x));
}

int Query(int x) {
  int ans = 0;
  for (; x; ans += tr[x], x -= lowbit(x));
  return ans;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n >> k, mx = 0;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i].x >> a[i].y >> a[i].c, b[i] = a[i].x;
    }
    // 下面都是离散化
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;
    fill(tr, tr + m + 1, 0);
    for (int i = 1; i <= n; ++ i) {
      a[i].x = lower_bound(b + 1, b + m + 1, a[i].x) - b;
    } 
    sort(a + 1, a + n + 1);
    // 插入哨兵
    for (int i = 1; i <= k; ++ i) {
      pos[i].clear();
      pos[i].insert(0), pos[i].insert(m + 1);
    }
    for (int i = 1, j; i <= n; i = j) {
      // 处理相同的 y 的宝石区间 [i, j)
      j = i;
      for (; j <= n && a[i].y == a[j].y; ++ j);
      // 对于相同的 y，先更新答案
      for (int k = i, l, r; k < j; ++ k) {
        auto it = pos[a[k].c].lower_bound(a[k].x);
        l = *prev(it), r = *it;
        mx = max(mx, Query(r - 1) - Query(l));
      }
      for (int k = i; k < j; ++ k) {
        pos[a[k].c].insert(a[k].x); // 插入障碍物集合
        Modify(a[k].x, 1); // 插入树状数组
      }
    }
    for (int i = 1, lst; i <= k; ++ i) { // 最后还要扫一遍
      lst = 0;
      for (auto k : pos[i]) {
        if (k) {
          mx = max(mx, Query(k - 1) - Query(lst)); // 高度无限大，只需要在障碍之间取即可
        } 
        lst = k;
      }
    }
    cout << mx << '\n';
  }
  return 0;
}