P9069 [Ynoi Easy Round 2022] Fallen Angel Operation TEST_98

Even though Mingming surpasses human intelligence and rules at the highest point, he always gives people some strange miracles. Of course, there will also be people who are dissatisfied and want to take back the throne of the primates. Many countries, organizations, and individuals challenge the superhuman machine in various ways. The many ways to make the godlike one in the sky fall down to the ground are called the Fallen Angel Operation. Among the methods used to seize divinity from the superhuman machine, there is a wildly imaginative psychological warfare. The hope is that he can put aside his identity as a machine and understand the beauty of humans being alive—like that. It is like a dog telling humans to become a dog, and I would sneer at that kind of dog. But unexpectedly, he accepted the invitation. Whether out of curiosity, to pass time, or out of sympathy, in short, he downgraded himself and sent a human avatar to this world. At that time, there were Earth-scale anomalies such as crustal movements or a cooling period. The demon race took the chance to rise up and spread the rust-iron fungus, bringing scientific civilization to an end. And the superhuman machine acted as if it had nothing to do with him. It seems he kept sending several avatars, but they all died in that kind of world. No matter how many times he tried, they fell halfway, dying before they could experience the beauty of being human. So the second wave of avatars appeared—cannot die! Putting the cart before the horse, right? That is no longer human. ...... I think it should not be like that. The superhuman machine is an existence capable of inventing magic, right? Although I feel that something like an immortal sounds very fake. But for such an amazing machine, if he really wanted to understand humans, he could just grab dozens or hundreds of people, install them onto himself as parts, and solve it immediately, right? ...... How should I put it, I feel... the idea of doing this to understand humans is a bit forced? If you think from the perspective of how intelligence that goes a level above, including humans, is born. Also, I believe the superhuman machine is a human who achieved transcendence through mechanization.  ...... The universe is very harsh: vacuum, extreme cold, radiation. Whether my magic power can work is completely unknown. Even if we want to build a rocket, who knows how many resources it will take to also perfect the pilot’s life-support equipment... But as long as we have an immortal, it can be solved. There is no mistake about that.

Given a sequence $a$ of length $n$, there are two types of operations, for a total of $m$ times: 1. Given $l$ $r$ $x$, for all $i$ such that $l \le i \le r$ and $a_i \neq x$, set $a_i \leftarrow a_i - x$. 2. Given $l$ $r$, query the sum of $a_i$ for all $i$ such that $l \le i \le r$ and $a_i \neq 0$.

The first line contains two integers $n, m$. The second line contains $n$ integers separated by spaces, representing the sequence $a$. Then follow $m$ lines, each containing three or four integers: If the input is `1 l r x`, it means applying operation $1$ to the interval $[l, r]$. If the input is `2 l r`, it means applying operation $2$ to the interval $[l, r]$. This problem is forced online. All input $l, r, x$ must be XORed with $lastans$, where $lastans$ is defined as the value of the answer of the previous query operation modulo $2^{20}$. If there has been no query operation before, then it is $0$.

For each operation $2$, output one line with one integer, representing the result modulo $2^{64}$.

Idea: nzhtl1477, Solution: nzhtl1477, Code: w33z8kqrqk8zzzx33, Data: w33z8kqrqk8zzzx33 For $5\%$ of the testdata, $n, m \le 1000$. For $30\%$ of the testdata, $n, m \le 5 \times 10^4$. For another $20\%$ of the testdata, $l = 1, r = n$. For another $20\%$ of the testdata, $x = 1$. Constraints: for $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $0 \le a_i, x \le 10^9$. Translated by ChatGPT 5