1500

Almost Increasing Subsequence

出处：CF1817A

题目大意：称不存在三个连续元素 $x,y,z$ 使得 $x \geq y \geq z$ 的序列为几乎递增序列。

给定 $a_1,\ldots,a_n$ 和 $q$ 个查询，对于每个查询，给出 $l,r$ 求 $a_l,\ldots,a_r$ 中几乎递增子序列的最长长度。

数据范围： $1 \leq n,q \leq 200000, 1 \leq a_i \leq 10^9,1 \leq l \leq r \leq n$

思路：这题赛时有零个头绪，全想到DP去了。

但是事实上是前缀和，唉唉。

贪心地想，只需要去除所有 $a_{i-1} \geq a_i \geq a_{i+1}$ 的 $a_i$ 即可，然后对于首尾和长度特判一下即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


void solve() {
    int n, q;
    int l, r;
    cin >> n >> q;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    vl pre(n);
    vector<bool> vis(n, false);
    rep(i, 1, n - 2) {
        if (a[i] <= a[i - 1] && a[i + 1] <= a[i]) vis[i] = true;
    }
    rep(i, 1, n - 1) { pre[i] = pre[i - 1] + vis[i]; }
    rep(i, 0, q - 1) {
        cin >> l >> r;
        l--, r--;
        if (r - l + 1 <= 2) {
            cout << r - l + 1 << endl;
            continue;
        }
        int tem = (r - l + 1) - (pre[r - 1] - pre[l]);
        cout << tem << endl;
    }
    return;
}