Processing math: 100%

POJ 2528 Mayor's posters

发表于 | 分类于 ，

每张海报的坐标范围0<=li<=ri<=107，线段树维护107长度的序列会爆内存。但是海报的数量1<=n<=10000，也就是线段树需要更新的区间端点数<=20000个，因此对坐标进行离散化处理。

这篇博客中指出普通的离散化在这个题中有些问题，考虑下面这组数据

1
2
3
1 10
1 4
6 10

离散化坐标映射后，1->0，4->1，6->2，10->3，更新完后，区间[0,1],[2,3]被后面两张海报覆盖，可见的海报数为2。而第一张海报在原始区间[5,5]仍然可见，答案应为3.

因此，如果排序后相邻两坐标xi,xi+1的差>1，则需要在两者之间插入一个数，使得离散后xi,xi+1的差也>1。区间(xi,xi+1)中可见的海报数为0或1，仅需要插入一个数，其信息在最终就能够被统计到。

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_N = 10000 + 10;
const int ST_SIZE = 1 << 17; // 40000

int n;
int L[MAX_N], R[MAX_N];
int change[ST_SIZE];
bool visible[MAX_N];

void init(int k, int l, int r) {
  memset(change, 0, sizeof(change));
}

void update(int k, int l, int r, int a, int b, int c) {
  if (b <= l || r <= a) {
    return;
  } else if (a <= l && r <= b) {
    change[k] = c;
  } else {
    int lc = 2 * k + 1, rc = 2 * k + 2;
    int m = (l + r) / 2;
    if (change[k]) {
      change[lc] = change[k];
      change[rc] = change[k];
      change[k] = 0;
    }
    update(lc, l, m, a, b, c);
    update(rc, m, r, a, b, c);
  }
}

void query(int k, int l, int r) {
  if (change[k]) visible[change[k]] = true;
  if (l == r - 1) {
    return;
  } else {
    if (change[k]) return;
    else {
      query(2 * k + 1, l, (l + r) / 2);
      query(2 * k + 2, (l + r) / 2, r);
    }
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    vector<int> p;
    for (int i = 1; i <= n; i++) {
      scanf("%d %d", L + i, R + i);
      p.push_back(L[i]);
      p.push_back(R[i]);
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    for (int i = p.size() - 1; i >= 1; i--) {
      if (p[i] != p[i - 1] + 1) p.push_back(p[i - 1] + 1);
    }
    sort(p.begin(), p.end());

    init(0, 0, p.size());
    for (int i = 1; i <= n; i++) {
      int l = lower_bound(p.begin(), p.end(), L[i]) - p.begin();
      int r = lower_bound(p.begin(), p.end(), R[i]) - p.begin();
      update(0, 0, p.size(), l, r + 1, i);
    }
    memset(visible, 0, sizeof(visible));
    query(0, 0, p.size());
    int res = 0;
    for (int i = 1; i <= n; i++) {
      if (visible[i]) res++;
    }
    printf("%d\n", res);
  }
  return 0;
}