{"problem":{"name":"幻梦 | Dream with Dynamic","description":{"content":"有一个长度为 $n$ 的序列，开始时第 $i$ 位为 $a_i$。你需要完成 $q$ 次操作： - `A l r x`，对于所有的 $l\\le i\\le r$，令 $a_i\\gets a_i+x$。 - `P l r`，对于所有的 $l\\le i\\le r$，令 $a_i\\gets\\operatorname{popcount}(a_i)$。 - `J p`，查询 $a_p$ 的值。 注：$\\o","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":10000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8969"},"statements":[{"statement_type":"Markdown","content":"有一个长度为 $n$ 的序列，开始时第 $i$ 位为 $a_i$。你需要完成 $q$ 次操作：\n\n- `A l r x`，对于所有的 $l\\le i\\le r$，令 $a_i\\gets a_i+x$。\n- `P l r`，对于所有的 $l\\le i\\le r$，令 $a_i\\gets\\operatorname{popcount}(a_i)$。\n- `J p`，查询 $a_p$ 的值。\n\n注：$\\operatorname{popcount}(x)$ 为 $x$ 的二进制表示中 $1$ 的个数。\n\n## Input\n\n第一行两个正整数 $n,q$。\n\n第二行 $n$ 个正整数 $a_1, a_2, \\ldots, a_n$。\n\n接下来 $q$ 行，每行描述一个操作，形如以下三种中的一种：\n\n- `A l r x`\n- `P l r`\n- `J p`\n\n## Output\n\n对于每个 `J` 操作，输出一行，一个整数，表示答案。\n\n[samples]\n\n## Background\n\n“那以后见到她，会不会笑出来啊？”\n\n“哈，一时半会见不到她的。”\n\n小时候说要一起去看尘寰间的人间烟火，有人欣然接受，长大了说遗忘过去，那人也没有反驳。\n\n其实吧，她们彼此明白，小时候在意的不是什么人间烟火，而是一起。\n\n黑夜里，没有早晨的绯红，也褪去了天边的白光，留下的是她心头的散不去的灰暗。没有星光璀璨，没有满天繁星，她不在乎。她在乎的是那个人心中闪烁的星辰大海。\n\n----\n\n察觉所谓规则秘密，不过取悦于创世神明，早已知晓光明同黑暗般腥风血雨\n\n## Note\n\n**【样例解释】**\n\n- 开始时，$a = [1, 2, 3, 4, 5]$。\n- 对询问 `J 2`，应回答 $a_2 = 2$。\n- 操作 `A 2 4 3` 后，$a = [1, 5, 6, 7, 5]$。\n- 对询问 `J 4`，应回答 $a_4 = 7$。\n- 操作 `P 1 4` 后，$a = [1, 2, 2, 3, 5]$。\n- 对询问 `J 3`，应回答 $a_3 = 2$。\n\n---\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 特殊限制 | 分值 |\n| :----------: | :----------: | :----------: |\n| 1 |$n,q\\le 2000$| 3 |\n| 2 |没有 `P` 操作| 7 |\n| 3 |没有 `A` 操作| 15 |\n| 4 |数据随机生成| 15 |\n| 5 |无特殊限制| 60 |\n\n对于全部数据，保证 $1\\leq n\\leq 3\\times 10^5$，$1 \\le q \\le 10^6$，$1 \\le l \\le r \\le n$，$1 \\le p \\le n$，$1\\le a_i, x\\le 10^9$。\n\n子任务 4 的随机方式：\n\n- 取 $n=3\\times 10^5$，$q=10^6$；\n- $a_i$ 从 $[1,10^9]$ 均匀随机选取；\n- 对于每一个操作：\n\t- 从 3 种操作中均匀随机选取一个；\n   - 如果是 `A` 操作，均匀随机从 $[1,n]$ 中选取 2 个整数，将较小的作为区间左端点，较大的作为区间右端点，再从 $[1,10^9]$ 中选取一个整数作为参数 `x`；\n   - 如果是 `P` 操作，均匀随机从 $[1,n]$ 中选取 2 个整数，将较小的作为区间左端点，较大的作为区间右端点；\n   - 如果是 `J` 操作，均匀随机从 $[1,n]$ 中选取一个整数作为参数 `p`。\n\n---\n\n**【提示】**\n\n本题最大 I/O 量达到 30 MiB，请注意 I/O 效率。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8969","tags":["线段树","洛谷原创","O2优化","洛谷月赛","均摊分析","线段树合并"],"sample_group":[["5 5\n1 2 3 4 5\nJ 2\nA 2 4 3\nJ 4\nP 1 4\nJ 3\n","2\n7\n2\n"]],"created_at":"2026-03-03 11:09:25"}}