#PQJ3435x17584. QOJ 3435_17584
QOJ 3435_17584
标题: 象形文字序列 - Problem - QOJ.ac
#17584. 象形文字序列
The problem was used in the following contests:
题目描述
一个研究团队正在研究象形文字序列的一些性质,他们将每个象形文字复杂程度表示成一个正整数,没有两个象形文字被表示的数一样。为了开展研究,他们采用了关于序列的如下概念。
对于一个给定长度为 n 下标从 1 开始的序列 A:
- A 能被称为排列,当且仅当 1,2,⋯,n 分别在 A 中有且仅有出现一次。
- 某个序列 B 被称为是 A 的子序列,当且仅当 B 能够通过移除 A 中的某些(也可能零个)元素而得到。
- A 的区间 [l,r] 是 Al,Al+1,⋯,Ar 构成的序列。
研究人员想知道一个排列 A 的区间 [li,ri] 的最长上升子序列的长度。
据说研究人员用了三天只会一个比较劣的做法。
输入格式
第一行输入两个正整数 n,q,表示排列大小和询问个数。
第二行输入 n 个正整数 ai,表示排列的元素。
接下来 q 行每行输入两个正整数 li,ri,表示查询的区间。
输出格式
输出第 q 行,每行输出一个正整数,表示最长的上升子序列的长度。
样例一
input
5 5
1 5 2 4 3
1 5
2 4
3 3
1 4
2 5
output
3
2
1
3
2
限制与约定
对于所有数据,保证 1≤n≤105,1≤q≤106,1≤ai≤n。
本题有 5 个子任务。只有该任务下测试点全部通过才能得到该子任务的分数。
子任务编号 子任务分数 特殊限制 1 5 ri−li≤10 2 25 n≤10000 3 30 li−1≤li,ri−1≤ri 4 30 a 在所有长度为 n 的排列中等概率选取 5 10 无特殊限制