P3774 [CTSC2017] 最长上升子序列

题目描述

猪小侠最近学习了最长上升子序列的相关知识。对于一个整数序列 $A =(a_1, a_2,\ldots , 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, \ldots, b_m)$,设 $C$ 是 $B_m$ 的子序列,且 $C$ 的最长上升子序列的长度不超过 $k$,则 $C$ 的长度最大能是多少? 猪小侠觉得这个问题太简单了,缺乏挑战,他决定提出一个更难的问题。于是他给了你这样一个序列 $B = (b_1, b_2,\ldots , b_n)$,以及若干次询问。每次询问会给定两个整数 $m$ 和 $k$,你需要对于 $B$ 序列的前 $m$ 个元素构成的序列 $B_m = (b_1, b_2, \ldots, b_m)$ 和 $k$ 回答上述问题。

输入格式

输出格式

说明/提示

【样例解释】 询问 $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$。 ![](https://cdn.luogu.com.cn/upload/pic/5487.png) 对于 $100\%$ 的数据, $1\leq n\leq 5\times 10^4$,$1\leq b_i\leq 5\times 10^4$,$1\leq q \leq 2\times 10^5$,$1\leq k_i \leq m_i \leq n$。