P3810. 三维偏序

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

考点

  • cdq分治
  • 树状数组

题解

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 50;
int n, k, bit[maxn], ans[maxn];

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

void add(int x, int v) {
  while (x <= k) bit[x] += v, x += lowbit(x);
}

int query(int x) {
  int res = 0;
  while (x > 0) res += bit[x], x -= lowbit(x);
  return res;
}

struct node {
  // sum_：与本元素不同的元素对其贡献
  // cnt_：与本元素相同的元素有几个（包括本元素）
  int sum_, cnt_;
  int a_, b_, c_;
  bool operator==(node &b) { return a_ == b.a_ && b_ == b.b_ && c_ == b.c_; }
} a[maxn];

bool cmpa(node &a, node &b) {
  return a.a_ < b.a_ || (a.a_ == b.a_ && a.b_ < b.b_) ||
         (a.a_ == b.a_ && a.b_ == b.b_ && a.c_ < b.c_);
}

bool cmpb(node &a, node &b) {
  return a.b_ < b.b_ || (a.b_ == b.b_ && a.c_ < b.c_);
}

void cdq(int l, int r) {
  if (l == r) return;
  int mid = (l + r) / 2;
  cdq(l, mid), cdq(mid + 1, r);
  int i = l, j = mid + 1;
  while (i <= mid && j <= r) {
    while (i <= mid && a[i].b_ <= a[j].b_) {
      add(a[i].c_, a[i].cnt_), ++i;
    }
    a[j].sum_ += query(a[j].c_), ++j;
  }
  while (i <= mid) add(a[i].c_, a[i].cnt_), ++i;
  while (j <= r) a[j].sum_ += query(a[j].c_), ++j;
  for (i = l; i <= mid; ++i) add(a[i].c_, -a[i].cnt_);
  sort(a + l, a + r + 1, cmpb);
}

int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i].a_ >> a[i].b_ >> a[i].c_;
  sort(a + 1, a + 1 + n, cmpa);
  int m = 0, cnt = 0;
  // 模拟unique函数
  for (int i = 1; i <= n; ++i) {
    ++cnt;
    if (!(a[i] == a[i + 1])) {
      a[++m] = a[i];
      a[m].cnt_ = cnt, cnt = 0;
    }
  }
  cdq(1, m);
  for (int i = 1; i <= m; ++i) ans[a[i].sum_ + a[i].cnt_ - 1] += a[i].cnt_;
  for (int i = 0; i < n; ++i) cout << ans[i] << endl;
  return 0;
}

思路

一维偏序是排序，二维偏序是排序+树状数组，三维偏序是排序+cdq+树状数组

本题下标没有限制，只是说i != j；如果是i < j，那么就是四维了

先对a排序，那么左半部分[l, mid]的a一定小于等于右半部分[mid+1, r]的a，a条件就成功降维了。

对左右两半各分治，分治之后的合并是最关键的部分；尽管左右两半部分先进行了分治，内部顺序可能是乱的；

但由于一开始我们是对a排序了的，[l, mid]的a还是必小于等于[mid+1, r]的a，不影响。

然后分别对[l, mid]、[mid+1, r]的b排序，令游标i归属[l, mid]，游标j归属[mid+1, r]。

只要j的b是大于等于i的b，i就一直往后移，并且把i的c纳入到树状数组去；

那么对于j而言，三维都满足条件的个数显然等于树状数组中[1, j的c]的个数。

注意！上述方法只考虑了不同元素之间的贡献，并没有考虑相同元素，举个例子：

3 2

1 1 1 1 1 1 2 2 2

如果按照上面的方法，答案是1 1 1，解释如下：

  • 第一个元素1 1 1没有满足三维条件的
  • 第二个元素1 1 1有一个满足三维条件的，即第一个元素
  • 第三个元素2 2 2有两个满足三维条件的，即第一、第二个元素

但答案应该是0 2 1，解释如下：

  • 第一个元素1 1 1有一个满足三维条件的，即第二个元素
  • 第二个元素1 1 1有一个满足三维条件的，即第一个元素
  • 第三个元素2 2 2有两个满足三维条件的，即第一、第二个元素

因为题目并没有限制i与j的大小关系所致。

可以发现，相同元素之间的贡献其实就等于相同元素个数 - 1

所以在正式做cdq分治之前，应该统计一下每种元素的个数，用cnt保存

所以最终得到式子：

本元素受到的贡献 = 不同元素对本元素的贡献 + 相同元素对本元素的贡献 = sum + cnt - 1