POJ3250 从多个方面考虑同一问题

发表于 分类于

有很多的方法过这题，以下介绍三种方法，主要思路是将序列反转（其实不反转也没什么），然后去找第 ii 个元素左边靠最右的比这个元素大的位置 jj，那么 i−j+1i-j+1 就是第 ii 个元素对应的解。

第一种方法：利用线段树动态更新，完成上部分的查询，复杂度 O(nlg⁡n)O(n \lg n)。

对线段树处理这类问题的方法就不详细说明了，想要了解的，看这篇文章

我的代码：

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

using namespace std;

const int MAX = 80001;
const int oo = 0x3f3f3f3f;

struct Node {
  int l, r, val;
} seg[MAX << 2];
int h[MAX];

void init(int k, int l, int r) {
  seg[k].l = l;
  seg[k].r = r;
  seg[k].val = -1;
  if (l == r) {
    return;
  }
  int mid = (l + r) >> 1;
  init(k << 1, l, mid);
  init(k << 1 | 1, mid + 1, r);
}

void add(int k, int idx) {
  if (seg[k].l == seg[k].r) {
    seg[k].val = idx;
    return;
  }
  int mid = (seg[k].l + seg[k].r) >> 1;
  if (idx <= mid)
    add(k << 1, idx);
  else
    add(k << 1 | 1, idx);
  if (seg[k << 1 | 1].val != -1 && h[seg[k << 1 | 1].val] >= h[seg[k << 1].val])
    seg[k].val = seg[k << 1 | 1].val;
  else
    seg[k].val = seg[k << 1].val;
}

int read(int k, int idx, int v) {
  if (seg[k].l > idx) return -1;
  if (h[seg[k].val] < v) return -1;
  if (seg[k].l == seg[k].r) return seg[k].val;
  int mid = (seg[k].l + seg[k].r) >> 1;
  if (idx > mid && h[seg[k << 1 | 1].val] >= v) {
    return read(k << 1 | 1, idx, v);
  } else {
    return read(k << 1, idx, v);
  }
}

int main() {
  int n;
  long long ret = 0;
  scanf("%d", &n);
  h[0] = oo;
  for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
  reverse(h + 1, h + n + 1);
  init(1, 0, n);
  add(1, 0);
  for (int i = 1; i <= n; i++) {
    ret += i - read(1, i - 1, h[i]) - 1;
    add(1, i);
  }
  printf("%lld\n", ret);
  return 0;
}

第二种方法：利用一个单调栈，栈内维护一个递减的区间，记录在此元素之前比其大的元素序列的下标。新的元素入队，如果栈顶元素大于这个入队元素，那么结果就加上这个元素的下标减去栈顶元素下标再减去 11，否则栈顶元素出栈，以此类推。算法复杂度是 O(n)O(n) 的。

算法实现其实很简单，只要维护一个栈，用 top 表示栈顶下标就可以了。

我的代码：

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

using namespace std;

const int MAX = 80005;
const int oo = 0x3f3f3f3f;
int st[MAX], h[MAX];

int main() {
  int n;
  scanf("%d", &n);
  h[0] = oo;
  for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
  reverse(h + 1, h + 1 + n);
  int top = 0;
  long long ret = 0;
  st[top++] = 0;
  for (int i = 1; i <= n; i++) {
    while (h[st[top - 1]] < h[i]) top--;
    ret += i - st[top - 1] - 1;
    st[top++] = i;
  }
  printf("%lld\n", ret);
  return 0;
}

第三种方法：利用并查集的思路直接做。记录 rir_i 表示第 ii 个元素可以到达的最右边的下标，那么每次利用下面的方式压缩路径：

1
2
r[i] = i;
while (h[i] > h[r[i] + 1]) r[i] = r[r[i] + 1];

细节处理看我的代码，算法复杂度是 O(n×α(n))O(n \times \alpha(n)) 的。

我的代码：

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

using namespace std;

const int MAX = 80005;
const int oo = 0x3f3f3f3f;
int r[MAX], h[MAX];

int main() {
  int n;
  long long ret = 0;
  scanf("%d", &n);
  h[n] = oo;
  for (int i = 0; i < n; i++) scanf("%d", &h[i]);
  r[n] = n;
  for (int i = n - 1; i >= 0; i--) {
    r[i] = i;
    while (h[i] > h[r[i] + 1]) r[i] = r[r[i] + 1];
    ret += r[i] - i;
  }
  printf("%lld\n", ret);
  return 0;
}

三个算法比较：

对于第一个算法肯定是最慢的，毕竟 O(nlg⁡n)O(n \lg n) 的时间复杂度加上线段树的较大常数，和下面两个 O(n)O(n) 或者近似 O(n)O(n) 的算法来比，会逊色很多。

从后两个算法运行时间上看，O(n×α(n))O(n \times \alpha(n)) 的第三种算法反而更快，可能是我单调栈常数太大了，或者我的序列反转过的原因。

​