#P14484. [2025年广东省队集训]修理

    ID: 13701 传统题 1500ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900数据结构线段树可持久化数学贪心ST表

[2025年广东省队集训]修理

问题描述

又到了小机器人维修时间!

由于工作损耗,小机器人可能会偏移了正常的行为设定,我们用 bib_i 表示每个小机器人的偏移值。你的任务是将所有小机器人恢复正常(即将所有偏移值变为 00)。你有一把脉冲枪来完成这项任务,脉冲枪初始脉冲值 x=0x = 0,单位时间内,你可以进行如下操作之一:

  • 将 xx 增加 11。
  • 对一个小机器人进行施加异或脉冲,即选择一个 ii,令 bi←bi⊕xb_i \leftarrow b_i \oplus x。

其中 ⊕\oplus 表示二进制下的异或运算。

现在,给定长度为 nn 的序列 aia_i 表示小机器人的偏移值,多次询问修理区间 [l,r][l,r] 中所有小机器人所需花费的最少时间。

输入格式

第一行三个整数 n,Q,tn,Q,t,分别表示小机器人数量、询问次数、是否强制在线。

第二行共 nn 个正整数,分别表示每个小机器人的偏移值 aia_i。

接下来 QQ 行,每行两个整数 li′,ri′l'_i,r'_i 代表一次询问。当 t=1t=1 时 li=li′,ri=ri′l_i = l'_i,r_i = r'_i。当 t=2t = 2 时,$l_i = \min(l'_i \oplus lst,r'_i \oplus lst),r_i = \max(l'_i \oplus lst,r'_i \oplus lst)$,其中 lstlst 表示上一次询问的答案(初始为 00)。

输出格式

共 QQ 行,第 ii 行表示第 ii 次修理所需的最少时间。

输入样例

7 6 1
5 4 3 5 7 7 7
1 4
4 7
3 7
1 7
2 6
1 1

输出样例

9
11
12
14
12
6

数据范围

对于 100%100\% 的数据,$1\leq n,Q \leq 2 \times 10^5,1\le l_i \le r_i\le n,1\le a_i < 2^{60}$。

测试点编号 nn QQ tt 特殊限制
1∼21\sim 2 ≤103\leq 10^3 11 无
3∼43\sim 4 ≤2×105\leq 2\times 10^5 AA
5∼65\sim 6 BB
7∼87\sim 8 5×1045\times 10^4 ≤5×104\leq 5\times 10^4 无
9∼109\sim 10 2×1052\times 10^5 ≤2×105\leq 2\times 10^5
11∼1311\sim 13 ≤5×104\leq 5\times 10^4 22
14∼1614\sim 16 ≤105\leq 10^5
17∼2017\sim 20 ≤2×105\leq 2\times 10^5

特殊性质 A: ∀i∈[1,n)\forall i \in [1,n),ai≤ai+1a_i \le a_{i+1}。

特殊性质 B: ∀i∈[1,Q]\forall i \in [1,Q],li=1,ri=il_i = 1, r_i = i。