此篇是從舊 Blog 搬過來。
Zerojudge a813 - 4. 城市觀測
題目敘述
有 N 棟房子。對於任意 AB 兩棟房子，只要 AB 中間沒有房子的高度超過 A 或 B，則 A 可看見 B。求 1 ~ N 每棟房子可看見的房子總數。
- 測資一，0 < N ≤ 300，0 < H[i] ≤ 1e5，3/17分
- 測資二，0 < N ≤ 5000，0 < H[i] ≤ 1e5，3/17分
- 測資三，0 < N ≤ 1e6，0 < H[i] ≤ 1e9，11/17分
範例測資
- N = 2，H = {1,1}，ans = 1+1 = 2
- N = 3，H = {1,2,3}，ans = 1+2+1 = 4
- N = 5，H = {5,2,3,4,4}，ans = 4+2+3+3+2 = 14
參考解法
「A 可看見 B」和「B 可看見 A」等價，因此只要計算一半就好了，也就是可以將問題簡化成，計算每棟房子往左看的sum x 2。
最直接的做法就是直接 O(N²) 掃過，但第三筆測資顯然需要 O(NlgN) 才有可能 AC。
因為先寫了 TIOJ 1176 Cows 這題，所以就想到用 stack 去維護遞減性，但因為 stack 無法很計算等號成立的部分，所以 google 了一下，恍然大悟，直接用 array 模擬 stack 解決了，還可以搭配 binary search 達到 O(NlgN) 的時間複雜度。
TIOJ 那題的複雜度是 O(N)，因為每個元素最多進出 stack 一次，超類似單調隊列！
為什麼要維護單調性？
假設我們是由左而右計算，每棟大樓都只能往左看，那只要某數右方有大於它的數，那它就不可能被更右方的數看到。 所以我們就是要維護一個左高右低的梯形/三角形。
每加入一個數，檢察它左邊的數，如果比他低，就不可能被更後面的數看見，也就可以 pop 掉，之後也不需要檢查。
而在 stack 裡的數，可以保證單調遞減，也就是中間不會有更高的數，所以只要比你低，一定能被看見，於是 pop 前，將 ans++。
檢查到一樣高的數時……
麻煩的地方就在這，你不知道在他之前有幾個數和他一樣，但一個一個 pop 再 push 進去實在很浪費時間，例如全部都一樣高的 case，效率會變 O(N²)。於是改成用array來操作，雖然不用 pop 再 push，但查找時一樣是 O(N²)。
二分搜優化
要徹底解決 O(N²)，還是需要二分搜啦！直接二分搜 stack 最後一個大於等於他的位置就可以加減出答案。
有單調性的東西就給他二分搜下去吧～
Code
1#include <bits/stdc++.h>
2using namespace std;
3typedef long long ll;
4#define maxn 1000005
5int a[maxn], st[maxn];
6int main() {
7 int n; scanf("%d",&n);
8 for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
9 ll ans = 0;
10 int top = 0;
11 for (int i = 1; i <= n; i++) {
12 if (top) {
13 //binary_search
14 int k = 0, left = 1, right = top;
15 while (left <= right) {
16 int mid = (left + right) >> 1;
17 if (st[mid] >= a[i])
18 k = max(mid, k), left = mid + 1;
19 else right = mid - 1;
20 }
21 ans += top - k;
22 top = k;
23 }
24 if (top) {
25 int k = 0, left = 1, right = top;
26 while (left <= right) {
27 int mid = (left + right) >> 1;
28 if (st[mid] > a[i])
29 k = max(mid, k), left = mid + 1;
30 else right = mid - 1;
31 }
32 ans += top - k;
33 if (k) ans++;
34 }
35 st[++top] = a[i];
36 }
37 printf("%lld\n", ans * 2);
38 return 0;
39}