UOJ Logo Universal Online Judge

UOJ

#301. 【CTSC2017】最长上升子序列

统计

猪小侠最近学习了最长上升子序列的相关知识。对于一个整数序列 $A=(a_1,a_2,\cdots,a_k)$,定义 $A$ 的子序列为:从 $A$ 中删除若干个元素后(允许不删,也允许将所有 $k$ 个元素都删除),剩下的元素按照原来的顺序所组成的序列。如果这个子序列的元素从左到右严格递增,则称它为 $A$ 的一个上升子序列。其中包含元素数量最多的上升子序列称为 $A$ 的最长上升子序列。例如,$(2,4,5,6)$ 和 $(1,4,5,6)$ 都是 $(2,1,1,4,7,5,6)$ 的最长上升子序列,长度都为 $4$。

现在猪小侠遇到了这样一个问题:给定一个序列 $B_m=(b_1,b_2,\cdots,b_m)$,设 $C$ 是 $B_m$ 的子序列,且 $C$ 的最长上升子序列的长度不超过 $k$,则 $C$ 的长度最大能是多少?

猪小侠觉得这个问题太简单了,缺乏挑战,他决定提出一个更难的问题。于是他给了你这样一个序列 $B=(b_1,b_2,\cdots,b_n)$,以及若干次询问。每次询问会给定两个整数 $m$ 和 $k$,你需要对于 $B$ 序列的前 $m$ 个元素构成的序列 $B_m=(b_1,b_2,\cdots,b_m)$ 和 $k$ 回答上述问题。

输入格式

第一行两个整数 $n,q$,其中 $n$ 是序列 B 的长度,$q$ 是询问次数。

第二行是空格隔开的 $n$ 个正整数 $b_1,b_2,\cdots,b_n$。

接下来 $q$ 行,其中第 $i$ 行包含两个整数 $m_i,k_i$,表示对 $m=m_i,k=k_i$ 进行询问。

输出格式

输出共 $q$ 行,按顺序每行一个整数作为回答。

样例一

input

11 6
9 6 3 1 5 12 8 4 2 2 2
5 1
7 2
9 1
9 2
11 1
11 11

output

4
6
5
8
7
11

explanation

询问1:对于序列$(9,6,3,1,5)$,可以选取子序列$(9,6,3,1)$,它的最长上升子序列长度为$1$。

询问2:对于序列$(9,6,3,1,5,12,8)$,可以选取子序列$(9,6,3,1,12,8)$,它的最长上升子序列长度为$2$。

询问3:对于序列$(9,6,3,1,5,12,8,4,2)$,可以选取子序列$(9,6,5,4,2)$,它的最长上升子序列长度为$1$。

询问4:对于序列$(9,6,3,1,5,12,8,4,2)$,可以选取子序列$(9,6,3,1,12,8,4,2)$,它的最长上升子序列长度为$2$。

询问5:对于序列$(9,6,3,1,5,12,8,4,2,2,2)$,可以选取子序列$(9,6,5,4,2,2,2)$,它的最长上升子序列长度为$1$。

询问6:对于序列$(9,6,3,1,5,12,8,4,2,2,2)$,可以选取子序列$(9,6,3,1,5,12,8,4,2,2,2)$,它的最长上升子序列长度为$3$。

样例二

见样例数据下载。

限制与约定

测试点 $n$ 约束
1$\le 50000$$k_i = 1$
2$\le 300$$k_i \le 2$
3$\le 3000$
4$\le 50000$$b_i \le 5$
5$b_i \le 8$
6$\le 100$$m_i = n$
7
8$\le 800$$m_i = n, k_i \le 10$
9$\le 1500$
10$\le 10000$$m_i = n, k_i \le 30$
11$\le 15000$$m_i = n, k_i \le 40$
12$\le 20000$$m_i = n, k_i \le 50$
13$k_i \ge 10000$
14$\le 8000$$m_i = n$
15$\le 25000$没有约束
16$\le 40000$
17$\le 45000$
18$\le 50000$
19
20

对于 $100\%$ 的数据,$1\le n\le 50000, 1\le b_i \le 50000$,$1 \le q \le 200000$,$1\le k_i \le m_i \le n$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载