← 返回题目列表

AtCoder · abc393_f

I. 前缀 LIS 查询

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 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\lbrace A_1, A_2,\dots,A_{R_i} \rbrace.

约束

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

输入

输入由标准输入按以下格式给出:

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

输出

打印 Q 行。的 i- 第行应包含以下问题的答案 i-第一个查询。


示例输入 1

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

示例输出 1

2
1
2
  • 第一个查询:对于序列 (2,4),最多包含所有元素的最长严格递增子序列 5 有长度 2.
    具体来说, (2,4) 符合资格。
  • 第二个查询:对于序列 (2,4,1,3,3),最多包含所有元素的最长严格递增子序列 2 有长度 1.
    具体来说, (2) 和 (1) 符合资格。
  • 第三个查询:对于序列 (2,4,1,3,3),最多包含所有元素的最长严格递增子序列 3 有长度 2.
    具体来说, (2,3) 和 (1,3) 符合资格。

示例输入 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