luogu#P5670. 秘籍-反复异或

    ID: 9692 远端评测题 500ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>位运算按位块状链表块状数组分块枚举暴力

秘籍-反复异或

题目描述

给定一个长为 nn 的序列,支持操作:

  • 1 l r x:将区间 [l,r][l,r] 的所有元素加 xx
  • 2 l r :查询区间 [l,r][l,r] 中所有元素异或和的后 mm 个二进制位的值。

输入格式

第一行三个正整数 n,m,qn,m,q,表示序列长度,位数,操作数。

第二行 nn 个非负整数,表示原始序列 aia_i

接下来 qq 行,每行若干个非负整数表示一个操作。

输出格式

对于每个 22 操作输出一行,一个非负整数表示答案。

10 2 10
0 1 0 0 1 0 2 2 0 1 
2 3 9
2 1 5
1 9 9 0
1 3 7 2
1 1 6 3
2 1 10
2 6 7
2 3 6
1 3 9 2
1 3 9 3

1
0
3
1
3

提示

【数据范围】
本题共 1010 个测试点。

对于测试点 131 \sim 31n,q10001\le n,q \le 1000
对于测试点 4,54,51m51 \le m \le 5
对于测试点 6106 \sim 10,设 kk 为测试点编号,有 m=km=k

对于 100%100\% 的数据,1n,q1051 \le n,q \le 10^51m101\le m \le 100ai,x<2m0\le a_i,x < 2^m

请注意常数优化。