题解 - Codeforces 1468A LaIS

另一个好想好写的做法，看题解区还没有就来一发。

简述题意

给定数列 $a_1,\ldots,a_n$，要求找到最长的子序列 $b_1,\ldots,b_m(m\ge 2)$ 满足 $\forall 1\le k\le m-2,\min(b_k,b_{k+1})\le \min(b_{k+1},b_{k+2})$。$1\le a_i\le n$，$\sum n\le 5\times 10^5$。

分析

经典思路是考虑动态规划，令 $f_i$ 为以第 $i$ 位为结尾的最大合法子序列长度。

假设 $i$ 的前驱是 $j$：

• $a_j\le a_i$ 则总是满足条件，直接用 $f_j+1$ 向 $f_i$ 贡献，从左往右扫的时候实时维护前缀 $\max$。
• $a_j > a_i$：令 $j$ 的前驱为 $k$，则 $\min(a_k, a_j)\le \min(a_j, a_i)$，即 $a_k\le a_i$。那就让 $j$ 越靠右越优。用单调栈找到每个 $i$ 对应的最靠右的 $j$ 满足 $a_j>a_i$，在 $j$ 处查询前缀 $\max$ 即可。

这里的前缀 $\max$ 就是：维护 $g_i$ 为以 $i$ 的值为结尾的最大 $f$ 值，这里的转移就是 $g$ 数组的前缀求 $\max$。不减地单点修改，求前缀 $\max$，可以用树状数组实现。时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

代码

实现时重复计入了 $a_j=a_i$ 的贡献，显然没关系。

#include <bits/stdc++.h>
using namespace std;

const int MXN = 500005;
int T, N, arr[MXN], stk[MXN], top, val1[MXN], mxv[MXN], ans;
vector<int> task[MXN];

int query(int p) {
  int v(0);
  while (p) v = max(v, mxv[p]), p -= p & -p;
  return v;
}
void setv(int p, int v) {
  while (p <= N) mxv[p] = max(mxv[p], v), p += p & -p;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> T;
  while (T--) {
    cin >> N;
    top = -1;
    for (int i(0); i != N; ++i) {
      cin >> arr[i];
      task[i].clear();
      val1[i] = 0;
      while (~top && arr[stk[top]] < arr[i]) --top;
      if (~top) task[stk[top]].push_back(i);
      stk[++top] = i;
    }
    for (int i(1); i <= N; ++i) mxv[i] = 0;
    ans = 0;
    for (int i(0); i != N; ++i) {
      ans = max(ans, val1[i] = max(val1[i], query(arr[i]) + 1));
      for (int j : task[i]) {
        val1[j] = max(val1[j], query(arr[j]) + 2);
      }
      setv(arr[i], val1[i]);
    }
    cout << ans << endl;
  }
  return 0;
}