走楼梯(walk)
题目背景
从一缕微光开始,不断变得更强。
题目描述
一组楼梯有 n 级台阶,按顺序的高度为 a1,…,an,高度可能参差不齐。布莱克可以跳过若干级台阶,但每次落脚的台阶必须比前一次严格更高。他希望走到的台阶数尽可能多,即选择高度序列的最长严格上升子序列。
他将看到 m 组结构相同的楼梯。每组都有一段区间 [l,r] 正在装修,区间内的台阶不能停留。对于每组楼梯,求只使用其余台阶时,最长严格上升子序列的长度。各组询问相互独立,不会永久删除原序列元素。
部分数据要求强制在线,需要用上一次答案解密当前询问。
输入格式
第一行两个整数 n,type。
第二行 n 个整数 a1,…,an,表示台阶高度。
第三行一个正整数 m。
接下来 m 行,每行两个整数 l′,r′:
- 若 type=0,则 l=l′,r=r′。
- 若 type=1,则 l=l′xorlastans,r=r′xorlastans。
其中 xor 表示按位异或,lastans 为上一次询问的答案,初始为 0。解密后的 [l,r] 是本组不能停留的台阶区间。
输出格式
输出 m 行,每行一个整数,表示对应询问的答案。
样例输入
5 0
6 2 4 3 5
3
2 4
1 3
4 4
样例输出
1
2
3
样例解释
- 第一次剩余 [6,×,×,×,5],最多选一个台阶,高度为 6 或 5。
- 第二次剩余 [×,×,×,3,5],可选高度 3,5。
- 第三次剩余 [6,2,4,×,5],可选高度 2,4,5。
数据范围
- 对于 20% 的数据,n,m≤1000。
- 另有 30% 的数据,type=0。
- 对于 70% 的数据(包含以上全部数据),n,m≤30000。
- 对于全部数据,1≤n,m≤100000,type∈{0,1},解密后 1≤l≤r≤n;所有输入数在 [0,109] 内。