{"problem":{"name":"[Ynoi Easy Round 2022] 堕天作战 TEST_98","description":{"content":"给定一个长为 $n$ 的序列 $a$，有两种操作，共 $m$ 次： 1. 给定 $l$ $r$ $x$，对于所有 $i$ 满足 $l\\le i\\le r$ 且 $a_i \\neq x$，$a_i\\leftarrow a_i-x$。 2. 给定 $l$ $r$，求对于所有 $i$ 满足 $l\\le i\\le r$ 且 $a_i\\neq 0$，$a_i$ 的和。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9069"},"statements":[{"statement_type":"Markdown","content":"给定一个长为 $n$ 的序列 $a$，有两种操作，共 $m$ 次：\n\n1. 给定 $l$ $r$ $x$，对于所有 $i$ 满足 $l\\le i\\le r$ 且 $a_i \\neq x$，$a_i\\leftarrow a_i-x$。\n2. 给定 $l$ $r$，求对于所有 $i$ 满足 $l\\le i\\le r$ 且 $a_i\\neq 0$，$a_i$ 的和。\n\n## Input\n\n第一行两个数 $n,m$。\n\n第二行 $n$ 个用空格隔开的数表示序列 $a$。\n\n之后 $m$ 行，每行三个或四个数：\n\n若输入为 `1 l r x`，则表示对区间 $[l,r]$ 进行一次 $1$ 操作，若输入为 `2 l r`，则表示对区间 $[l,r]$ 进行一次 $2$ 操作。\n\n本题强制在线，所有输入的 $l,r,x$ 均需要异或 $lastans$，其定义为上一次询问操作得到的答案对 $2^{20}$ 取模后的值，若之前没有询问操作，则为 $0$。\n\n## Output\n\n对每个 $2$ 操作，输出一行一个数表示答案对 $2^{64}$ 取模后的结果。\n\n[samples]\n\n## Background\n\n明明超越人智，君临了至高点，却总是给些奇怪的奇迹。当然也会有不满的人出现，想要取回灵长的宝座。\n\n有许多的国家，组织，个人，用各种方法挑战超人机械。要让天上宛如神的他，堕落于地的众多手段——被称作是堕天作战。\n\n为了从超人机械手中抢夺神性而被用上的手段里，有一个天马行空的心理战。希望他能抛下机械的身份理解人类活着的美好——这样。\n\n那就像是狗在对着人类说当条狗吧，像那种狗我会嗤之以鼻的。但是没想到，他接受了那个邀约。不管是好奇心，打发时间，或是同情，总之他将降级为人类的分身送到这世上了。\n\n那时正逢地壳变动或是寒冷化之类的地球规模的异变，而魔人在此时趁机崛起，撒下了腐铁菌，让科学文明画下句点。而超人机械则是一副事不关己的样子。\n\n分身似乎不断地送了好几位来，但都死了，在那种世界里。不管试多少次都在途中倒下，还没体会到人类的美好就死了。\n\n于是出现了分身第二弹——不会死！本末倒置对吧，那已经不是人类了。\n\n......\n\n我想应该不是那样。\n\n超人机械是足以发明出魔法的存在吧？虽然我觉得不死者这种存在听起来很假。\n\n但这么厉害的机械，若真的想理解人类，只要随便抓个几十，几百人，当作零件装到自家身上，马上就能解决了吧？\n\n......\n\n该怎么说呢，我觉得...为了理解人类这个见解，有点牵强了呢？\n\n从包括人类在内更上一层楼的知性，是如何诞生的角度来思考的话。\n\n而且我认为，超人机械，是透过机械化——达成超越的人类。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/t2yh2k2u.png)\n\n......\n\n宇宙是很严峻的，真空，极寒，辐射，我的魔力能否起作用，完全是未知数。\n\n就算是要打造火箭，也不知道要耗费多少资源才能连飞行员的生存设备也一并完善...\n\n但只要有不死者就能解决，不会错的。\n\n## Note\n\nIdea：nzhtl1477，Solution：nzhtl1477，Code：w33z8kqrqk8zzzx33，Data：w33z8kqrqk8zzzx33\n\n对于 $5\\%$ 的数据，$n,m\\le 1000$。\n\n对于 $30\\%$ 的数据，$n,m\\le 5\\times10^4$。\n\n对于另外 $20\\%$ 的数据，$l=1,r=n$。\n\n对于另外 $20\\%$ 的数据，$x=1$。\n\n对于 $100\\%$ 的数据 $1\\le n,m \\le 5\\times10^5, 0\\le a_i, x \\le10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9069","tags":["2022","O2优化","Ynoi"],"sample_group":[["10 10\n0 1 2 3 4 5 6 7 8 9\n1 5 10 5\n2 1 10\n1 23 29 23\n2 21 19\n1 1048573 1048570 1048574\n2 1048573 1048566\n1 1048573 1048569 1048575\n2 1048575 1048564\n1 1048572 1048567 1048572\n2 1048572 1048567","20\n18446744073709551615\n18446744073709551614\n18446744073709551613\n18446744073709551606"]],"created_at":"2026-03-03 11:09:25"}}