問題描述
平面上 n 個點 (xi, yi)，座標值在 [1, 100000]，無相同 x 或 y。選若干點構成集合 S，按 x 排序連成折線，統計連續上升/下降段數 f(S)。給定 k，求 f(S) = k 的集合數，模 100007。
限制：n ≤ 50000, k ≤ 10。
解題思路
- 按 x 排序點。
- y 座標離散化（或直接用座標值，範圍 1e5）。
- 動態規劃 + 樹狀數組優化轉移。
狀態定義
f[i][j][0]：前 i 個點，選 j 段，最後一段**下降**的方案數。f[i][j][1]：前 i 個點，選 j 段，最後一段**上升**的方案數。
轉移方程
f[i][j][0] = Σ (f[k][j][0] + f[k][j-1][1]) (k < i 且 y[k] > y[i])
f[i][j][1] = Σ (f[k][j][1] + f[k][j-1][0]) (k < i 且 y[k] < y[i])
對於固定 j，需快速查詢 y > y[i] 或 y < y[i] 的前綴和 → 樹狀數組/線段樹維護。
核心程式碼框架
#include
using namespace std;
const int MAXN = 100005;
const int MOD = 100007;
struct Point { int x, y; } a[MAXN];
int n, k, b[MAXN]; // b 為離散化後的 y
int f[MAXN][11][2]; // 或用兩個 BIT 數組滾動
// BIT 模板
struct BIT {
vector t;
BIT(int n=0): t(n+1, 0) {}
void add(int x, int v) { for(; x
關鍵優化點
- 滾動陣列降低空間至
O(k·MAXN)。
- 兩棵 BIT 分別維護「上升」與「下降」狀態的前綴和。
- 離散化 y 座標，適配 BIT 索引範圍。
複雜度
- 時間：
O(n·k·log n)，n=5e4, k=10 可行。
- 空間：
O(n·k) 或 O(MAXN)。
