#P5066. [Ynoi2014] 人人本着正义之名

[Ynoi2014] 人人本着正义之名

题目背景

那是什么?
【不是第六兽,是新的兽?】
【我从来没见过那种玩意啊】

【全员退避】
【现已确认出现预料之外的兽】
【根据这一事态,将作战确认为失败,放弃15号岛】
怎么会...

我和他约好了的
绝对要活着回去

对他说“我回来了”,然后品尝黄油蛋糕
所以,要是世界终结的话我会很伤脑筋的

融没于晨雾之中的树林
啊...?

【牛奶迹.耀眼花瓣.狂风气团】
【挂于墙上的鲱鱼.倒立的刺猬.袋中的风琴】
这是什么...?

你其实...很想战斗的对吧
虽然我不知道你有什么打算,但是已经够了

你已经不用战斗了
因为你的战斗,已经由我,由我们继承下来了
【其实我很感激你】
【一直以来,我心里就只想着死】

【渴望去往那些等着我回去的家伙身边,这是我唯一的愿望】
【但是遇见你们之后,我有了一些改变】
【我又开始渴望获得一个容身之处了】
【遇见你之后,我得到了一些救赎】
【能够等到你平安归来,我现在...】
【嗯,可以说,感受到了一丝幸福】
啊...?

【不...等一下,你别这么露骨地和我拉开距离啊】
【也别露出一副“这个不知廉耻的生物是怎样”的表情啊】
【不过话说回来,你观察我观察地很仔细啊】
哈哈...
因为喜欢上了嘛~


【由不得我啊】
你要去的话我会生气的,我会大发雷霆的
【珂朵莉...】

【对不起】
我等你

我会等着你的,所以一定要回来哦

【我保证,一定会回来的】

说好了哦~

题目描述

你需要帮珂朵莉维护一个长为 nn01序列 aa,有 mm 个操作:

  • 1 l r:把区间 [l,r][l,r] 的数变成 00
  • 2 l r:把区间 [l,r][l,r] 的数变成 11
  • 3 l r[l,r1][l,r-1] 内所有数 aia_i,变为 aia_iai+1a_{i+1} 按位或的值,这些数同时进行这个操作。
  • 4 l r[l+1,r][l+1,r] 内所有数 aia_i,变为 aia_iai1a_{i-1} 按位或的值,这些数同时进行这个操作。
  • 5 l r[l,r1][l,r-1] 内所有数 aia_i,变为 aia_iai+1a_{i+1} 按位与的值,这些数同时进行这个操作。
  • 6 l r[l+1,r][l+1,r] 内所有数 aia_i,变为 aia_iai1a_{i-1} 按位与的值,这些数同时进行这个操作。
  • 7 l r:查询区间 [l,r][l,r] 的和。

本题强制在线,每次的 l,rl,r 需要 xor\operatorname{xor} 上上次答案 ,如果之前没有询问,则上次答案为 00

输入格式

第一行两个整数表示 nnmm

第二行 nn 个整数表示序列 aa

之后 mm 行,每行三个整数 opt,l,ropt,l,r,表示是哪一种操作以及操作对应的区间。

输出格式

对于每个查询操作输出一行一个数表示答案。

5 5
0 1 0 0 1
3 2 5
5 2 5
2 2 2
6 1 5
7 1 5
1

提示

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477

序列每次的样子:

0 1 0 0 10\ 1\ 0\ 0\ 1

0 1 0 1 10\ 1\ 0\ 1\ 1

0 0 0 1 10\ 0\ 0\ 1\ 1

0 1 0 1 10\ 1\ 0\ 1\ 1

0 0 0 0 10\ 0\ 0\ 0\ 1

0 0 0 0 10\ 0\ 0\ 0\ 1

对于 30%30\% 的数据,n,m1000n,m\leq 1000

对于 50%50\% 的数据,n,m105n,m\leq 10^5

对于另外 30%30\% 的数据,操作和序列均随机生成。

对于另外 10%10\% 的数据,n,m106n,m\leq 10^6

对于 100%100\% 的数据,1n,m3×1061\leq n,m\leq 3 \times 10^60ai10\leq a_i\leq 1