题目描述
小 W 维护一排不断向右延伸的花田。每朵花有一个高度和一个品种。
初始有 n 朵花。第 i 朵花的高度为 hi,品种编号为 ti,它们按顺序排列并编号为 1,2,…,n。接下来进行 m 次操作:
1 l r x:取出区间 [l,r] 中所有满足 hi≤x 的花,保持它们在原序列中的相对顺序。将取出的品种序列划分成若干个连续段,使得同一段内品种相同,输出段数。若没有取出任何花,答案为 0。
2 x y:在序列末尾追加一朵高度为 x、品种为 y 的花。
本题强制在线。记上一次查询的答案为 last,初始 last=0。输入中的每个参数都需要先与 k×last 按位异或,得到实际参数后再执行操作。追加操作不会修改 last;查询完成后,用本次答案更新 last。
输入格式
第一行包含三个整数 n,m,k。
第二行包含 n 个整数 h1,h2,…,hn,第三行包含 n 个整数 t1,t2,…,tn。
接下来 m 行描述操作。操作类型为 1 时,后面有三个编码参数;操作类型为 2 时,后面有两个编码参数。
输出格式
对于每个操作 1,输出一行一个整数,表示查询结果。
样例 1 输入
4 3 0
2 5 1 4
1 2 1 2
1 1 4 3
2 3 2
1 1 5 5
样例 1 输出
1
4
样例 2 输入
2 3 1
1 2
1 1
1 1 2 2
2 2 3
1 0 2 2
样例 2 输出
1
2
样例 3 输入
3 2 0
5 5 5
1 1 1
1 1 3 4
1 1 3 5
样例 3 输出
0
1
数据范围
记所有操作完成后序列的长度为 n′。对于全部数据,满足:
- 1≤n′,m≤500000;
- 1≤hi,ti,x,y≤109;
- 1≤l≤r≤n′;
- op∈{1,2},且 0≤k≤1000。
输入中的编码参数均为非负的 32 位有符号整数;解码后的参数满足题目给出的范围。
| 数据类别 |
分值 |
测试点 |
附加条件 |
| A |
15 |
1∼3 |
1≤n′,m≤103 |
| B |
20 |
4∼7 |
1≤n′,m≤3×105 且 k=0 |
| C |
8∼11 |
1≤n′,m≤3×105,每次查询都有 l=1 |
| D |
15 |
12∼14 |
1≤n′,m≤105 |
| E |
15∼17 |
1≤n′,m≤3×105 |
| F |
18∼20 |
1≤n′,m≤5×105 |