#2130. 最长上升子序列

    ID: 2130 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest304来源:qoj.ac数据:公开样例动态规划

最长上升子序列

最长上升子序列

题目描述

IOI 2017 中国代表队选拔赛暨全国青少年信息学奥林匹克精英赛 第二试最长上升子序列(lis) 最长上升子序列(lis) 【问题描述】 猪小侠最近学习了最长上升子序列的相关知识。对于一个整数序列A = (a1, a2, · · · , ak),定义A 的子序列为:从A 中删除若干个元素后(允许不删,也允 许将所有k 个元素都删除),剩下的元素按照原来的顺序所组成的序列。如果这个 子序列的元素从左到右.严.格递增,则称它为A 的一个上升子序列。其中包含元素数 量最多的上升子序列称为A 的最长上升子序列。例如,(2, 4, 5, 6) 和(1, 4, 5, 6) 都是 (2, 1, 1, 4, 7, 5, 6) 的最长上升子序列,长度都为4。 现在猪小侠遇到了这样一个问题:给定一个序列Bm = (b1, b2, · · · , bm),设C 是Bm 的子序列,且C 的最长上升子序列的长度.不.超.过k,则C 的长度最大能是多少? 猪小侠觉得这个问题太简单了,缺乏挑战,他决定提出一个更难的问题。于是他给 了你这样一个序列B = (b1, b2, · · · , bn),以及若干次询问。每次询问会给定两个整数m 和k,你需要对于B 序列的前m 个元素构成的序列Bm = (b1, b2, · · · , bm) 和k 回答上述 问题。 【输入格式】 从文件lis.in 中读入数据。 第一行两个整数n, q,其中n 是序列B 的长度,q 是询问次数。 第二行是空格隔开的n 个正整数b1, b2, · · · , bn。 接下来q 行,其中第i 行包含两个整数mi, ki,表示对m = mi, k = ki 进行询问。 【输出格式】 输出到文件lis.out 中。 输出共q 行,按顺序每行一个整数作为回答。 【样例1 输入】 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 第4 页 共8 页 IOI 2017 中国代表队选拔赛暨全国青少年信息学奥林匹克精英赛 第二试最长上升子序列(lis) 【样例1 输出】 4 6 5 8 7 11 【样例2】 见选手目录下的lis/lis2.in 与lis/lis2.ans。 【样例解释】 询问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。 第5 页 共8 页 IOI 2017 中国代表队选拔赛暨全国青少年信息学奥林匹克精英赛 第二试最长上升子序列(lis) 【数据规模】 测试点 约束 n ≤50000 ki = 1 1 ≤300 2 ki ≤2 ≤3000 3 bi ≤5 4 ≤50000 bi ≤8 5 6 mi = n ≤100 7 ≤800 8 mi = n, ki ≤10 ≤1500 9 mi = n, ki ≤30 ≤10000 10 mi = n, ki ≤40 ≤15000 11 mi = n, ki ≤50 12 ≤20000 ki ≥10000 13 mi = n ≤8000 14 ≤25000 15 ≤40000 16 ≤45000 17 没有约束 18 ≤50000 19 20 对于100% 的数据,1 ≤n ≤50000, 1 ≤bi ≤50000,1 ≤q ≤200000,1 ≤ki ≤mi ≤n。 第6 页 共8 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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
4
6
5
8
7
11