则$f$:$C$.
代码:
```c++
int ans = 0;
int f[N];
f[0] = 0;
up(i, 1, n){
int l = 0, r = ans + 1;
while(r - l > 1){
int m=(l + r) >> 1;
if(a[i] op f[m]) l = m; //op起决定性作用
else r = m;
}
ans = max (ans, l + 1);
f[l + 1] = a[i];
}
```
$$ O(nlogn) $$
# 二分
```cpp
ll l = /*minimum valid value*/; // must be valid
ll r = /*maximum valid value*/; // must be valid
while (l <= r) { // <=
ll mid = l + ((r – l) >> 1); // (l + r) / 2 is also avalible
if (check(mid)) r = mid – 1; // -1
else l = mid + 1; // +1
}
return l;
```
# 多边形的面积
令 $(x_0,y_0)=(x_n,y_n)$, 则
$S = \frac{1}{2}\sum_{i=0}^{n-1}{x_i y_{i+1}}+y_i x_{i+1}