题目描述
给出一个长度为 m 的排列 b 和一个长度为 n 的序列 a。
如果一个序列 S,满足其按位置从左到右依次匹配 b 的一个区间从左到右的位置,那么我们说 S 是一个「优美序列」。
给出 q 次询问。每次询问给出两个整数 l 和 r。你需要找到一个 a 的 [l,r] 子区间中的一个最长的满足「优美序列」条件的子序列长度。注意子序列可以不连续。
输入格式
- 第一行输入四个整数 m,n,q,T,其中 n,m,q 的含义见「题目描述」,T 表示是否强制在线。
- 第二行输入 m 个整数 b1,b2,⋯,bm。
- 第三行输入 n 个整数 a1,a2,⋯,an。
- 接下来 q 行每行输入两个整数 l′,r′。若 T=1,则你需要将 l′ 和 r′ 按位异或 lastans 来得到真正的 l,r。其定义为上一次询问操作得到的答案,若之前没有询问操作,则为 0。否则若 T=0,则 l=l′,r=r′。
输出格式
- 输出共 q 行。
- 第 i 行输出一个整数,表示第 i 次询问的答案。
提示
样例解释
lastans 解密后的询问为:
数据范围
Subtask1234分值10153045n,m≤1001053×1053×105q≤104105106106T=1101特殊性质AA−−Subtask 依赖−1−2,3
- 特殊性质 A:保证 ai,bi,l,r 在数据范围内均匀随机。
对于 100% 的数据,1≤l≤r≤n≤3×105,1≤ai≤m≤3×105,1≤q≤1×106,T∈{0,1}。