#2253. 象形文字序列

    ID: 2253 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>TEAM赛事:contest3435来源:qoj.ac数据:公开样例线段树

象形文字序列

象形文字序列

题目描述

标题: 象形文字序列 - 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 无特殊限制

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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