HDU1506 线段树做法

发表于 分类于

这道题本来是用 dp 做的，这几天都在练 dp，看了一下，可以用线段树来做，就尝试了一下，虽然不好写，但是还是可以做的 - -。

这题的关键在于预处理出每个方格可以向左向右分别扩展多少长度，记录 lil_i 和 rir_i 分别表示第 ii 个格子可以向左向右扩展的格子数，那么如果选中了第 ii 个格子，面积就是 (li+ri+1)×hi(l_i + r_i + 1) \times h_i，这样最后线性扫一遍就可以了。

lil_i 的求法，最直接的方法就是枚举，从该格子向左枚举，找到第一个比它小的格子，这个格子右边的都是可扩展的。

这样做复杂度是 O(n2)O(n^2) 的，对于 10510^5 的数据量来说是不可以接受的，所以我们需要优化，用线段树维护每个区间的最小值，我们会发现这个格子事实上就是 ii 号格子左边区间的最靠右边的比它小的格子，这样就可以轻松转化为给定区间求区间中最靠右的比 xx 小的元素的 idid。

rir_i 的求法类似，所以要维护两棵线段树。

最后问题迎刃而解，还要注意的就是需要用到 long long 类型。。。

我的代码：

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int MAX = 100010;

struct Seg {
  int l, r, id;
  int mid() { return (l + r) >> 1; }
} lt[MAX << 2], rt[MAX << 2];
int l[MAX], r[MAX];
long long h[MAX];

void initl(int k, int l, int r) {
  lt[k].l = l;
  lt[k].r = r;
  lt[k].id = -1;
  if (l == r) return;
  int mid = lt[k].mid();
  initl(k << 1, l, mid);
  initl(k << 1 | 1, mid + 1, r);
}

void initr(int k, int l, int r) {
  rt[k].l = l;
  rt[k].r = r;
  rt[k].id = -1;
  if (l == r) return;
  int mid = rt[k].mid();
  initr(k << 1, l, mid);
  initr(k << 1 | 1, mid + 1, r);
}

void setl(int k, int idx) {
  if (lt[k].l == lt[k].r) {
    lt[k].id = idx;
    return;
  }
  int mid = lt[k].mid();
  if (idx <= mid)
    setl(k << 1, idx);
  else
    setl(k << 1 | 1, idx);
  if (lt[k << 1 | 1].id != -1 && h[lt[k << 1 | 1].id] < h[lt[k << 1].id]) {
    lt[k].id = lt[k << 1 | 1].id;
  } else {
    lt[k].id = lt[k << 1].id;
  }
}

void setr(int k, int idx) {
  if (rt[k].l == rt[k].r) {
    rt[k].id = idx;
    return;
  }
  int mid = rt[k].mid();
  if (idx <= mid)
    setr(k << 1, idx);
  else
    setr(k << 1 | 1, idx);
  if (rt[k << 1].id != -1 && h[rt[k << 1].id] < h[rt[k << 1 | 1].id]) {
    rt[k].id = rt[k << 1].id;
  } else {
    rt[k].id = rt[k << 1 | 1].id;
  }
}

int readl(int k, int a, int b, long long x) {
  // if(lt[k].id!=-1)printf("Left %d %d %I64d\n",lt[k].l,lt[k].r,h[lt[k].id]);
  if (h[lt[k].id] > x) return -1;
  if (lt[k].l == lt[k].r) return lt[k].id;
  int mid = lt[k].mid();
  if (b <= mid)
    return readl(k << 1, a, b, x);
  else if (a > mid)
    return readl(k << 1 | 1, a, b, x);
  else {
    if (lt[k << 1 | 1].id != -1 && h[lt[k << 1 | 1].id] <= x) {
      return readl(k << 1 | 1, a, b, x);
    } else {
      return readl(k << 1, a, b, x);
    }
  }
}

int readr(int k, int a, int b, long long x) {
  if (h[lt[k].id] > x) return -1;
  if (rt[k].l == rt[k].r) return rt[k].id;
  int mid = rt[k].mid();
  if (b <= mid)
    return readr(k << 1, a, b, x);
  else if (a > mid)
    return readr(k << 1 | 1, a, b, x);
  else {
    if (rt[k << 1].id != -1 && h[rt[k << 1].id] <= x) {
      return readr(k << 1, a, b, x);
    } else {
      return readr(k << 1 | 1, a, b, x);
    }
  }
}

int main() {
  int n;
  while (scanf("%d", &n), n) {
    for (int i = 0; i < n; i++) {
      scanf("%I64d", &h[i]);
    }
    initl(1, 0, n - 1);
    initr(1, 0, n - 1);
    l[0] = 0;
    r[n - 1] = 0;
    setl(1, 0);
    setr(1, n - 1);
    for (int i = 1; i < n; i++) {
      int id = readl(1, 0, i - 1, h[i]);
      setl(1, i);
      if (id == -1) {
        l[i] = i;
      } else {
        l[i] = i - id - 1;
        if (h[i] == h[id]) l[i] += l[id] + 1;
      }
    }
    for (int i = n - 2; i >= 0; i--) {
      int id = readr(1, i + 1, n - 1, h[i]);
      setr(1, i);
      if (id == -1) {
        r[i] = n - 1 - i;
      } else {
        r[i] = id - i - 1;
        if (h[i] == h[id]) r[i] += r[id] + 1;
      }
    }
    // for(int i=0;i<n;i++)printf("%d ",l[i]);puts("");
    // for(int i=0;i<n;i++)printf("%d ",r[i]);puts("");
    long long ret = 0;
    for (int i = 0; i < n; i++) {
      ret = max(ret, (l[i] + r[i] + 1) * h[i]);
    }
    printf("%I64d\n", ret);
  }
  return 0;
}