#PQJ3435x17584. QOJ 3435_17584

    ID: 2926 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2025 集训线段树

QOJ 3435_17584

标题: 象形文字序列 - Problem - QOJ.ac

#17584. 象形文字序列

Statistics

The problem was used in the following contests:

题目描述

一个研究团队正在研究象形文字序列的一些性质,他们将每个象形文字复杂程度表示成一个正整数,没有两个象形文字被表示的数一样。为了开展研究,他们采用了关于序列的如下概念。

对于一个给定长度为 n 下标从 1 开始的序列 A:

  1. A 能被称为排列,当且仅当 1,2,⋯,n 分别在 A 中有且仅有出现一次。
  2. 某个序列 B 被称为是 A 的子序列,当且仅当 B 能够通过移除 A 中的某些(也可能零个)元素而得到。
  3. 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 无特殊限制