CF1550C 题解

## 前言 [题目传送门！](https://www.luogu.com.cn/problem/CF1550C) [更好的阅读体验？](https://liangbowen.blog.luogu.org/solution-cf1550c-TJ) 比赛时，这题写了一个 $O(n^3)$ 算法，然后就过了。 以为是数据水，实际上可以证明时间复杂度是 $O(n)$ 的。 ## 思路 关键是一个结论：当 $i < j < k$ 时，若 $a_i, a_j, a_k$ 单调不降或单调不升，则三元组 $(a_i, i), (a_j, j), (a_k, k)$ 必定是坏的。 为什么呢？画个图就很容易理解了。  同理，单调不增也是这样的。 所以，我们利用这一点 $O(n^2)$ 实现 `check` 函数。 ```cpp const int N = 2e5 + 5; int a[N]; bool chk(int l, int r) // [l,r] 区间是否是坏的 { for (int i = l; i < r; i++) for (int j = l; j < i; j++) //j<i<r { if (a[j] <= a[i] && a[i] <= a[r]) return true; if (a[j] >= a[i] && a[i] >= a[r]) return true; //符号反过来 } return false; } ``` 接着打个尺取，即可在 $O(n \times n^2)$ 的时间内完成程序。 ```cpp void solve() { int n; long long cnt = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int l = 1, r = 1; r <= n; r++) //顺序枚举右端点，左端点尺取 { for (; l <= r && chk(l, r); l++); cnt += (r - l + 1); } printf("%lld\n", cnt); } ``` 那为什么可以跑过去呢？原因在于，$\texttt{check()}$ 函数不会执行这么多次，实际是趋于 $O(1)$ 的！ 画一个图，可以发现，**不会**有长度大于等于 $5$ 的好子段。 所以这个方法去掉常数，就是 $O(n)$ 的。那么就可以欢快地打出代码了。 ## 完整代码 ```cpp #include <iostream> #include <cstdio> using namespace std; const int N = 2e5 + 5; int a[N]; bool chk(int l, int r) { for (int i = l; i < r; i++) for (int j = l; j < i; j++) { if (a[j] <= a[i] && a[i] <= a[r]) return true; if (a[j] >= a[i] && a[i] >= a[r]) return true; //符号反过来 } return false; } void solve() { int n; long long cnt = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int l = 1, r = 1; r <= n; r++) { for (; l <= r && chk(l, r); l++); cnt += (r - l + 1); } printf("%lld\n", cnt); } int main() { int T; scanf("%d", &T); while (T--) solve(); return 0; } ``` 希望能帮助到大家！