题目详情题解（0）讨论（0）提交记录（0）

AT_abc393_f.[ABC393F] Prefix LIS Query

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $ N $ 的整数序列 $ A=(A_1,A_2,\dots,A_N) $。

请处理 $ Q $ 个查询。第 $ i\ (1 \leq i \leq Q) $ 个查询如下：

  • 给定整数 $ R_i $ 和 $ X_i $。求数列 $ (A_1,A_2,\dots,A_{R_i}) $ 的（不一定连续的）子序列中，满足严格单调递增且所有元素不超过 $ X_i $ 的最长长度。保证 $ X_i \geq \min{ A_1, A_2, \dots, A_{R_i} } $。

输入格式

输入通过标准输入给出，格式如下：

$ N $ $ Q $
$ A_1 $ $ A_2 $ $ \dots $ $ A_N $
$ R_1 $ $ X_1 $
$ R_2 $ $ X_2 $
$ \vdots $
$ R_Q $ $ X_Q $

输出格式

输出 $ Q $ 行。第 $ i\ (1 \leq i \leq Q) $ 行输出第 $ i $ 个查询的答案。

输入输出样例

  • 输入#1

    5 3
2 4 1 3 3
2 5
5 2
5 3

    输出#1

    2
1
2

  • 输入#2

    10 8
2 5 6 5 2 1 7 9 7 2
7 8
5 2
2 3
2 6
7 3
8 9
9 6
8 7

    输出#2

    4
1
1
2
1
5
3
4

说明/提示

约束条件

  • $ 1 \leq N, Q \leq 2 \times 10^5 $
  • $ 1 \leq A_i \leq 10^9 $
  • $ 1 \leq R_i \leq N $
  • $ \min{ A_1, A_2, \dots, A_{R_i} } \leq X_i \leq 10^9 $
  • 输入中所有值均为整数

样例解释 1

  • 第 1 个查询：数列 $ (2,4) $ 中严格单调递增且所有元素不超过 $ 5 $ 的最长子序列长度为 $ 2 $。具体来说，子序列 $ (2,4) $ 满足条件。
  • 第 2 个查询：数列 $ (2,4,1,3,3) $ 中严格单调递增且所有元素不超过 $ 2 $ 的最长子序列长度为 $ 1 $。具体来说，子序列 $ (2) $ 或 $ (1) $ 满足条件。
  • 第 3 个查询：数列 $ (2,4,1,3,3) $ 中严格单调递增且所有元素不超过 $ 3 $ 的最长子序列长度为 $ 2 $。具体来说，子序列 $ (2,3) $ 或 $ (1,3) $ 满足条件。

翻译由 DeepSeek R1 完成

输入解题思路，AI测评打分。不知道怎么写?

首页