#P6898. 走楼梯

    ID: 6729 传统题 1500ms 1024MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理最长上升子序列前后缀分解数据结构树状数组离散化根号分块块内排序同向双指针前后缀最值CF2400

走楼梯

走楼梯(walk)

题目背景

从一缕微光开始,不断变得更强。

题目描述

一组楼梯有 nn 级台阶,按顺序的高度为 a1,…,ana_1,\ldots,a_n,高度可能参差不齐。布莱克可以跳过若干级台阶,但每次落脚的台阶必须比前一次严格更高。他希望走到的台阶数尽可能多,即选择高度序列的最长严格上升子序列。

他将看到 mm 组结构相同的楼梯。每组都有一段区间 [l,r][l,r] 正在装修,区间内的台阶不能停留。对于每组楼梯,求只使用其余台阶时,最长严格上升子序列的长度。各组询问相互独立,不会永久删除原序列元素。

部分数据要求强制在线,需要用上一次答案解密当前询问。

输入格式

第一行两个整数 n,typen,\mathrm{type}。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n,表示台阶高度。

第三行一个正整数 mm。

接下来 mm 行,每行两个整数 l′,r′l',r':

  • 若 type=0\mathrm{type}=0,则 l=l′l=l',r=r′r=r'。
  • 若 type=1\mathrm{type}=1,则 l=l′xorlastansl=l'\mathbin{\mathrm{xor}}\mathrm{lastans},r=r′xorlastansr=r'\mathbin{\mathrm{xor}}\mathrm{lastans}。

其中 xor 表示按位异或,lastans\mathrm{lastans} 为上一次询问的答案,初始为 00。解密后的 [l,r][l,r] 是本组不能停留的台阶区间。

输出格式

输出 mm 行,每行一个整数,表示对应询问的答案。

样例输入

5 0
6 2 4 3 5
3
2 4
1 3
4 4

样例输出

1
2
3

样例解释

  • 第一次剩余 [6,×,×,×,5][6,\times,\times,\times,5],最多选一个台阶,高度为 66 或 55。
  • 第二次剩余 [×,×,×,3,5][\times,\times,\times,3,5],可选高度 3,53,5。
  • 第三次剩余 [6,2,4,×,5][6,2,4,\times,5],可选高度 2,4,52,4,5。

数据范围

  • 对于 20%20\% 的数据,n,m≤1000n,m\le1000。
  • 另有 30%30\% 的数据,type=0\mathrm{type}=0。
  • 对于 70%70\% 的数据(包含以上全部数据),n,m≤30000n,m\le30000。
  • 对于全部数据,1≤n,m≤1000001\le n,m\le100000,type∈{0,1}\mathrm{type}\in\{0,1\},解密后 1≤l≤r≤n1\le l\le r\le n;所有输入数在 [0,109][0,10^9] 内。