P4198 楼房重建

发表于 分类于 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 4 分钟

考点

  • 线段树

题解

见思路

思路

普通想法

单点修改，区间询问，考虑线段树。

设斜率等于h(y) / y，如果点(y, h(y))要被看到，那么斜率肯定比之前的最大斜率还大。

设s代表当前区间最大值，c代表当前区间，从区间左端点仰望可以看见的建筑数量。

合并时，左孩子的c可以直接继承到父结点，因为左孩子的左端点是l，父结点的左端点也是l，

右孩子的c则不可以直接继承到父结点，因为右孩子是以mid + 1为左端点，而父结点的左端点是l，

即这行代码：

1
c[p] = c[lc] + f(rc, mid + 1, r, id[lc]);

也就是说，左孩子的加入会对右孩子的答案有如下影响：

假设当前父结点的区间为[l, r]，左孩子为lc，区间为[l, mid]； 右孩子为rc，区间为[mid + 1, r]

  1. 如果lc的斜率最大值，大于rc的左孩子斜率最大值。

    显然是无法从父结点的左端点l看见rc左孩子的任一房子，因为全被挡住了；但右孩子情况未知。

    这种情况下，rc的左孩子无法对答案有贡献，递归进rc的右孩子，也就是这行代码：

    1
    return 0 + f(rc, mid + 1, r, x);

  2. 如果lc的斜率最大值，小于rc的左孩子斜率最大值。

    此时lc就无法对rc的右孩子有影响，且rc的右孩子根据的左端点就是mid + 1，

    那么就可以把rc的右孩子的贡献并入答案中，然后再对rc左孩子进行递归。

    1
    return f(lc, l, mid, x) + (c[p] - c[lc]);

    但是要注意！！！！贡献绝对不是c[rc右孩子]，绝对不是！！！！！！！！！！！！！！！！！！！！！

    再次观察代码，我们自始至终都没有直接保存过右孩子的贡献，都是左孩子贡献+递归右孩子的结果，没有可加性！

    1
    c[p] = c[lc] + f(rc, mid + 1, r, id[lc]);

    最重要的是，c[rc右孩子]是rc右孩子以(mid + 1 + r) >> 1为左端点得到的结果，我们现在需知道rc右孩子以mid + 1为左端点时的贡献，完全就是两码事。

    所以，需要使用c[rc] - c[rc左孩子]得到c[rc右孩子]

最终得到代码：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50;
#define lc (p << 1)
#define rc (p << 1 | 1)
int n, m, h[maxn];
// 线段树
// id：最大斜率的h数组下标
// c：能看到的楼房个数
int id[maxn << 2], c[maxn << 2];

// x下标的斜率是否大于y下标的斜率
inline bool g(int x, int y) {
  if (!y) return h[x];
  return (ll)h[x] * y > (ll)h[y] * x;
}

int f(int p, int l, int r, int x) {
  if (l == r) return g(l, x);
  int mid = (l + r) >> 1;
  if (g(id[lc], x))
    return f(lc, l, mid, x) + (c[p] - c[lc]);
  else
    return 0 + f(rc, mid + 1, r, x);
}

void update(int p, int l, int r, int x, int v) {
  if (l == r) {
    h[x] = v;
    id[p] = c[p] = l;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) update(lc, l, mid, x, v);
  if (x > mid) update(rc, mid + 1, r, x, v);
  id[p] = g(id[lc], id[rc]) ? id[lc] : id[rc];
  c[p] = c[lc] + f(rc, mid + 1, r, id[lc]);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  int x, v;
  while (m--) {
    cin >> x >> v;
    update(1, 1, n, x, v);
    cout << c[1] << endl;
  }
  return 0;
}

升级想法

很多时候并没有可减性，比如取极值，按位与或等等。

所以可以改一下定义，c代表当前区间，rc的可见房屋数量；f是每个区间的总可见房屋数量。

1
2
3
4
5
6
7
8
int f(int p, int l, int r, int x) {
  if (l == r) return g(l, x);
  int mid = (l + r) >> 1;
  if (g(id[lc], x))
    return f(lc, l, mid, x) + c[p];
  else
    return 0 + f(rc, mid + 1, r, x);
}

这样一来，就不存在减法了。

总代码如下：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 50;
#define lc (p << 1)
#define rc (p << 1 | 1)
int n, m, h[maxn];
// 线段树
// id：最大斜率的h数组下标
// c：右子树能看到的楼房个数
int id[maxn << 2], c[maxn << 2];

// x下标的斜率是否大于y下标的斜率
inline bool g(int x, int y) {
  if (!y) return h[x];
  return (ll)h[x] * y > (ll)h[y] * x;
}

int f(int p, int l, int r, int x) {
  if (l == r) return g(l, x);
  int mid = (l + r) >> 1;
  if (g(id[lc], x))
    return f(lc, l, mid, x) + c[p];
  else
    return 0 + f(rc, mid + 1, r, x);
}

void update(int p, int l, int r, int x, int v) {
  if (l == r) {
    h[x] = v;
    id[p] = l;
    c[p] = 1;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) update(lc, l, mid, x, v);
  if (x > mid) update(rc, mid + 1, r, x, v);
  id[p] = g(id[lc], id[rc]) ? id[lc] : id[rc];
  c[p] = f(rc, mid + 1, r, id[lc]);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  int x, v;
  while (m--) {
    cin >> x >> v;
    update(1, 1, n, x, v);
    cout << f(1, 1, n, 0) << endl;
  }
  return 0;
}

参考文献

小粉兔大佬的思路，未来还需要磨砺啊~