题目地址：洛谷：P1970 花匠 – 洛谷 | 计算机科学教育新生态

题目描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数$h_1, h_2, \dots, h_n$。设当一部分花被移走后，剩下的花的高度依次为$g_1, g_2, \dots, g_n$，则栋栋希望下面两个条件中至少有一个满足：
条件A：对于所有$1 \leq i \leq m/2$，有$g_{2i} > g_{2i-1}$，同时对于所有的$1 \leq i \leq m/2$，有$g_{2i} > g_{2i+1}$
条件B：对于所有$1 \leq i \leq m/2$，有$g_{2i} < g_{2i-1}$，同时对于所有的$1 \leq i \leq m/2$，有$g_{2i} < g_{2i+1}$
注意上面两个条件在$m=1$时同时满足，当$m>1$时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。

一句话题意

给你一个正整数序列，找出其中最长的摆动子序列。

输入输出格式

输入格式：
第一行包含一个整数n，表示开始时花的株数。
第二行包含n个整数，依次为$h_1, h_2, \dots, h_n$，表示每株花的高度。

输出格式：
一个整数m，表示最多能留在原地的花的株数。

输入输出样例

输入样例#1：

5
5 3 2 1 2

输出样例#1：

3

说明

【输入输出样例说明】
有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。

【数据范围】
对于 20% 的数据，$n \leq 10$；
对于 30% 的数据，$n \leq 25$；
对于 70% 的数据，$n \leq 1000, 0 \leq h_n \leq 1000$；
对于 100% 的数据，$n \leq 100,000, 0 \leq h_n \leq 1,000,000$，所有的$h_n$随机生成，所有随机数服从某区间内的均匀分布。

题解

对于70%这一档数据，有一个很暴力的DP思路。设dp[i][0]为第i株花结尾且该花为摆动序列中的峰值（极大值）时摆动序列的最大长度，dp[i][0]为第i株花结尾且该花为摆动序列中的谷值（极小值）时摆动序列的最大长度。
DP转移时，需要从i之前的花中找到dp[i][0]和dp[i][1]的最大值来计算。下面是形式化的转移方程

$$ \begin{matrix} dp[i][0] = \operatorname{max}_{1 \leq j < i, h_j < h_i} \{ dp[j][1] \} + 1 \\ dp[i][1] = \operatorname{max}_{1 \leq j < i, h_j > h_i} \{ dp[j][0] \} + 1 \end{matrix}$$

答案即是所有DP值中的最大值。
这是一个很好想的暴力做法，但是它的复杂度达到了$O(n^2)$，转移的复杂度为$O(n)$，无法通过100%的数据。

接下来我们考虑优化转移。我们用权值线段树维护“对应权值的DP值最大值”这样一个数据，每一次转移时，利用权值范围即可直接查出上述最大值。而每次转移统计完毕后，只需要把新的DP值插入线段树中指定的权值位置上即可。由于需要两种最大值（dp[i][0]和dp[i][1]），我们可以建立两棵线段树分别管理两种DP值。这种优化可以使转移复杂度降至$O(\log n)$，从而将总复杂度降至$O(n \log n)$，可以通过本题。

事实上，很多题解使用的简单$O(n)$DP存在利用随机数据较弱混过去的成分，读者在阅读这些题解时会存有疑惑，这是因为它们的做法实际上是错解，存在被忽视的特殊情况。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <algorithm>
#include <vector>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc(); 
    while (c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

// variables

const int MAXN = 100005;

int n, N, h[MAXN], f0, f1, ans = 0;
std::vector<int> tmp;

// seg tree

struct Node {
    int val, lch, rch;
} tree[MAXN << 3];

int rt0, rt1, tot = 0;

inline int build(int l, int r) {
    int p = ++tot;
    if(l == r) {
        return p;
    }
    int mid = (l + r) >> 1;
    tree[p].lch = build(l, mid);
    tree[p].rch = build(mid + 1, r);
    return p;
}

inline void modify(int p, int l, int r, int x, int v) {
    if(l == r) {
        tree[p].val = std::max(tree[p].val, v);
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(tree[p].lch, l, mid, x, v);
    else modify(tree[p].rch, mid + 1, r, x, v);
    tree[p].val = std::max(tree[tree[p].lch].val, tree[tree[p].rch].val);
}

inline int query(int p, int l, int r, int ll, int rr) {
    if(ll > rr) return 0;
    if(l == ll && r == rr) {
        return tree[p].val;
    }
    int mid = (l + r) >> 1;
    if(rr <= mid) return query(tree[p].lch, l, mid, ll, rr);
    else if(ll > mid) return query(tree[p].rch, mid + 1, r, ll, rr);
    else return std::max(query(tree[p].lch, l, mid, ll, mid), query(tree[p].rch, mid + 1, r, mid + 1, rr));
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        h[i] = readint();
        tmp.push_back(h[i]);
    }
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    for(int i = 1; i <= n; i++) {
        h[i] = std::lower_bound(tmp.begin(), tmp.end(), h[i]) - tmp.begin() + 1;
    }
    N = tmp.size();
    rt0 = build(1, N);
    rt1 = build(1, N);
    for(int i = 1; i <= n; i++) {
        f0 = std::max(1, query(rt1, 1, N, 1, h[i] - 1) + 1);
        f1 = std::max(1, query(rt0, 1, N, h[i] + 1, N) + 1);
        ans = std::max(ans, std::max(f0, f1));
        modify(rt0, 1, N, h[i], f0);
        modify(rt1, 1, N, h[i], f1);
    } 
    printf("%d", ans);
    return 0;
}