前言

除了 A 題，唯一一道一遍過的題。

題目大意

我們定義滿足以下所有條件的一個長度為 $N$ 的序列 $A=(A_1,A_2,\dots ,A_N)$ 為波浪序列：

• $N\ge 4$（其實滿足后面就必須滿足這個條件）。
• $A_1\le A_2$（小心不要忘了這個條件）。
• 有且只有一個峰。
• 有且只有一個谷。

現在有個長度為 $N$ 的序列 $P$，求有多少個連續的子段是波浪序列。

思路

我們看一下條件——有且只有一個峰、一個谷。但是，整個序列里面會有許多峰、許多谷。然后，我們會從中選取一個峰、一個谷和一些其他類別的元素構成波浪序列。顯然，我們要記下所有峰、所有谷的位置。默認按從小到大順序記。

接下來，我們枚舉選取子段的右端點，從第一個既包含峰又包含谷的位置開始，一直枚舉到 $N$。考慮左端點可能的取值范圍。前面通過從小到大的順序暗示了這里的重要算法——二分。二分什么呢？左端點下邊界？上邊界？都可以。因為它是上下邊界都與峰谷的位置有關，而確定上邊界的峰一定“緊挨著”確定下邊界的峰（指的是中間不會有別的峰），谷也是同理。式子自己想想吧！不會可以看代碼。

代碼

請點擊 這里 查看 AC 記錄。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;int n, p[300010];
int c1, v1[300010]; // peak
int c2, v2[300010]; // valley
int s1[300010];
int s2[300010];int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> p[i];for (int i = 2; i < n; i++){s1[i] = s1[i - 1];if (p[i - 1] < p[i] && p[i] > p[i + 1])v1[++c1] = i, s1[i]++;s2[i] = s2[i - 1];if (p[i - 1] > p[i] && p[i] < p[i + 1])v2[++c2] = i, s2[i]++;}if (!c1 || !c2){cout << "0" << endl;return 0;}long long ans = 0;for (int i = max(v1[1], v2[1]) + 1; i <= n; i++){int p1 = lower_bound(v1 + 1, v1 + c1 + 1, i) - v1 - 1;int p2 = lower_bound(v2 + 1, v2 + c2 + 1, i) - v2 - 1;
//		if (p1 < 0 || p2 < 0) p1 = p2 = 0;
//		cout << i << " " << p1 << " " << p2 << ": " << endl;
//		cout << " - " << v1[p1] << " " << v2[p2] << endl;
//		cout << " - " << v1[p1 - 1] << " " << v2[p2 - 1] << endl;if (v1[p1] > v2[p2]) continue;int vmx = max(v1[p1 - 1], v2[p2 - 1]) - 1;int vmn = min(v1[p1], v2[p2]) - 1;vmx = max(vmx, 0);if (i - vmx < 4) continue;if (i - vmn + 1 < 4) vmn = i - 3;ans += vmn - vmx;
//		cout << i << " " << vmx << " " << vmn << endl;}cout << ans << endl;return 0;
}

總結

時間復雜度 $O(N?\log N)$，二分很好用。