#CW40. Sunflower(sunflower)

Sunflower(sunflower)

题目描述

小 W 维护一排不断向右延伸的花田。每朵花有一个高度和一个品种。

初始有 nn 朵花。第 ii 朵花的高度为 hih_i,品种编号为 tit_i,它们按顺序排列并编号为 1,2,…,n1,2,\dots,n。接下来进行 mm 次操作:

  • 1 l r x:取出区间 [l,r][l,r] 中所有满足 hi≤xh_i \le x 的花,保持它们在原序列中的相对顺序。将取出的品种序列划分成若干个连续段,使得同一段内品种相同,输出段数。若没有取出任何花,答案为 00。
  • 2 x y:在序列末尾追加一朵高度为 xx、品种为 yy 的花。

本题强制在线。记上一次查询的答案为 last,初始 last=0。输入中的每个参数都需要先与 k×lastk \times \text{last} 按位异或,得到实际参数后再执行操作。追加操作不会修改 last;查询完成后,用本次答案更新 last。

输入格式

第一行包含三个整数 n,m,kn,m,k。

第二行包含 nn 个整数 h1,h2,…,hnh_1,h_2,\dots,h_n,第三行包含 nn 个整数 t1,t2,…,tnt_1,t_2,\dots,t_n。

接下来 mm 行描述操作。操作类型为 11 时,后面有三个编码参数;操作类型为 22 时,后面有两个编码参数。

输出格式

对于每个操作 11,输出一行一个整数,表示查询结果。

样例 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′n'。对于全部数据,满足:

  • 1≤n′,m≤5000001 \le n',m \le 500000;
  • 1≤hi,ti,x,y≤1091 \le h_i,t_i,x,y \le 10^9;
  • 1≤l≤r≤n′1 \le l \le r \le n';
  • op∈{1,2}\text{op} \in \{1,2\},且 0≤k≤10000 \le k \le 1000。

输入中的编码参数均为非负的 3232 位有符号整数;解码后的参数满足题目给出的范围。

数据类别 分值 测试点 附加条件
A 15 1∼31\sim 3 1≤n′,m≤1031 \le n',m \le 10^3
B 20 4∼74\sim 7 1≤n′,m≤3×1051 \le n',m \le 3\times 10^5 且 k=0k=0
C 8∼118\sim 11 1≤n′,m≤3×1051 \le n',m \le 3\times 10^5,每次查询都有 l=1l=1
D 15 12∼1412\sim 14 1≤n′,m≤1051 \le n',m \le 10^5
E 15∼1715\sim 17 1≤n′,m≤3×1051 \le n',m \le 3\times 10^5
F 18∼2018\sim 20 1≤n′,m≤5×1051 \le n',m \le 5\times 10^5