#1445. 幻梦 | Dream with Dynamic

幻梦 | Dream with Dynamic

题目描述

有一个长度为 nn 的序列,开始时第 ii 位为 aia_i。你需要完成 qq 次操作:

  • A l r x,对于所有的 l≤i≤rl\le i\le r,令 ai←ai+xa_i\gets a_i+x。
  • P l r,对于所有的 l≤i≤rl\le i\le r,令 ai←popcount⁡(ai)a_i\gets\operatorname{popcount}(a_i)。
  • J p,查询 apa_p 的值。

注:popcount⁡(x)\operatorname{popcount}(x) 为 xx 的二进制表示中 11 的个数。

输入格式

第一行两个正整数 n,qn,q。

第二行 nn 个正整数 a1,a2,…,ana_1, a_2, \ldots, a_n。

接下来 qq 行,每行描述一个操作,形如以下三种中的一种:

  • A l r x
  • P l r
  • J p

输出格式

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

样例

5 5
1 2 3 4 5
J 2
A 2 4 3
J 4
P 1 4
J 3
2
7
2

题目来源:洛谷 P8969