【eJOI2020】考试（dp & 树状数组优化）

时间：2021-08-31 07:32:29

Description

\(n\) 个正整数排成一列，每个位置 \(i\) 有一个初始值 \(A_i\) 以及目标值 \(B_i\)。

一次操作可以选定一个区间 \([l, r]\)，并将区间内所有数赋值为 \(\max_{i\in[l, r]} A_i\)。

你可以进行任意次操作，每次操作基于上次操作的结果。

求结果若干次操作后，使得与操作后的值与目标值相同的位置数最大化。

Hint

\(1\le n\le 10^5, 1\le A_i, B_i\le 10^9\)。

原题数据过于奇妙于是就直接取最大值反正能做。官方那个三合一做法真的 /no

Solution

首先，我们不难求出对于每个 \(i\in[1, n]\)，该位置可以向左侧取到目标值 \(B_i = A_j\) 的第一个位置 \(L_i = j(\le i)\) 或者不存在，同理对于右侧 \(R_i\) 我们也这么干。

为什么我们只取第一个位置呢？显然可能存在多个可取的位置，不过注意到我们对位置 \(i\) 向 \(j\) 进行一次取值操作之后，会对中间的这些值造成影响。我们希望成功的取值操作尽可能多，那么影响的范围自然是越少越好了。

观察到一个性质，对于一个 \(i\)，如果 \(L_i\) （\(R_i\) 同理不再赘述）存在，说明 \(j\in[L_i +1, i]\) 这个区间的所有 \(A_j\) 的值都小于 \(A_{L_i}\)。那么一次操作下去，所有这个区间内的值都会失效，如果有像“从 \(A_j\) 取值到 \(k(<i)\)”这样的操作那必然不能同时与当前这个同时执行。

于是我们尝试大力将题目转化：有两排点，每排 \(n\) 个，对于第一排每个点 \(i\) 向第二排的第 \(L_i, R_i\) 个点分别连一条边。若选取一个第一排的点 \(i\)，那么需要至少选中连接 \(i\) 的两条或一条边的一条边（没有边则不能选）。要求选中的边两两不相交（除端点外），求最多选取第三个第一排的点。

发现当 \(A_i\) 互不相同时，每个点最多连出去 \(1\) 条边，这就是个经典的 LIS 问题，不过稍加拓展就可以得到本题的正解。

还是令 \(f(i, j)\) 为处理到第一排前 \(i\) 个点，第二排涉及到的点编号最大的为 \(j\)，可以选出第一排点个数的最大值。那么转移比较简单：

\[f(i, L_i) \leftarrow \max_{j \le L_i} \{f(i-1, j)\} +1, \qquad f(i, R_i) \leftarrow \max_{j \le R_i} \{f(i-1, j)\} +1
\]

不难发现把 \(i\) 滚掉之后实质上就是一个前缀 \(\max\)，于是使用树状数组优化为 \(O(n\log n)\)。

Code

/*

 * Author : _Wallace_

 * Source : https://www.cnblogs.com/-Wallace-/

 * Problem : eJOI2020 Exam

 */

#include <algorithm>

#include <cstdio>

#include <set>

#include <vector>

using namespace std;

const int N = 1e5 + 5;

int n;

int A[N], B[N];

int L[N], R[N];

int tr[N]; // 树状数组求前缀 max

inline void upd(int p, int v) {

  for (; p <= n; p += p & -p) tr[p] = max(tr[p], v);

}

inline int get(int p) {

  int v = 0;

  for (; p; p -= p & -p) v = max(tr[p], v);

  return v;

}

signed main() {

  scanf("%d", &n);

  for (int i = 1; i <= n; i++) scanf("%d", A + i);

  for (int i = 1; i <= n; i++) scanf("%d", B + i);

  vector<pair<int, int> > tmp(n * 2);

  set<int> rec({0, n + 1});

  for (int i = 1; i <= n; i++) tmp[i - 1] = {A[i], i};

  for (int i = 1; i <= n; i++) tmp[i + n - 1] = {B[i], -i};

  sort(tmp.begin(), tmp.end(), greater<pair<int, int> >());

  for (auto it : tmp) {

    if (it.second < 0) {

      int l = *rec.lower_bound(-it.second);

      if (A[l] == it.first) R[-it.second] = l;

      int r = *--rec.upper_bound(-it.second);

      if (A[r] == it.first) L[-it.second] = r;

    } else rec.insert(it.second);

  } // 求 L & R

  for (int i = 1; i <= n; i++) { // 同步更新

    int l = get(L[i]), r = get(R[i]);

    if (L[i]) upd(L[i], l + 1);

    if (R[i]) upd(R[i], r + 1);

  }

  printf("%d\n", get(n));

  return 0;

}

相关文章