题目描述
一个长为 n 的非负整数序列 a,支持以下两个操作:
1 l r x
:把区间 [l,r] 中所有 x 的倍数除以 x。2 l r
:查询区间 [l,r] 的和。
本题强制在线,每次的 l,r,x 需要 xor 上上次答案,如果之前没有询问,则上次答案为 0。
输入格式
第一行两个整数表示 n,m。
第二行 n 个非负整数表示 ai。
之后 m 行每行一个操作。
1 l r x
:把区间 [l,r] 中所有 x 的倍数除以 x。2 l r
:查询区间 [l,r] 的和。
输出格式
对于每次询问,输出一行一个整数表示答案。
样例 #1
样例输入 #1
5 2 1 2 3 4 5 1 1 5 2 2 1 5
样例输出 #1
12
提示
1≤n,m≤105,0≤ai≤5×105,解密后的 x,l,r 满足 1≤x≤5×105,1≤l≤r≤n。
Idea:nzhtl1477
Solution:nzhtl1477
Code:nzhtl1477,mrsrz
Data:nzhtl1477,mrsrz