P4231 Three-Step Surekill

(3) The Old Capital Leaving the narrow cave, the view suddenly opened up. Unusual snowflakes drifted in the sky. In contrast to the previous confinement, there was now a bustling marketplace, with the clinking of wine bowls audible. This was a small society made up of the oni, who were disliked by humans, and other youkai, a scene of harmony and joy. Eh? Not far away, some dense tiny dots appeared, like big grains of dust swirling in the air. Getting closer, it finally became clear. Horned oni gathered together, watching another oni’s performance. That “dust cloud” was actually danmaku. One of Yuugi’s moves: within three steps, wherever she passes, danmaku converge, leaving almost no chance of survival. To strengthen this skill, Yuugi would attack a row of pillars. Although the pillars of the Old Hell were incredibly sturdy, it was still safer to first figure out how much damage such a sequence of attacks would cause to the pillars, and this could also help evaluate the effectiveness of practice. Yuugi decided to discuss it with the other oni... “I know the kappa clan on Youkai Mountain has a magical tool called a computer; maybe we can borrow it,” said Suika. So the oni of the Old Hell decided to ask Nitori Kawashiro to help. “Do you want to record the damage levels of all pillars?” Nitori asked. After further inquiries, Nitori found that they only needed the damage levels of the pillars after all attacks were completed. Having understood the task, Nitori extracted the important parts and wrote them down in her work notebook: (See Problem Description for the recorded content.) Thus the experiment began. Amid earth-shaking collisions, after Yuugi completed each round of attacks, Nitori faithfully recorded the damage inflicted on each pillar. Yuugi, meanwhile, waited for the recording to be completed before proceeding to the next round. On the ground, dusk approached. “I don’t want to stay here until late at night, or I won’t be able to get home,” thought Nitori, her hands still repeatedly entering newly generated information into the computer. “Do I really have to record, one by one, the damage to each pillar after every round of attacks? Is there a more efficient way?” This thought flashed through Nitori’s mind... (The rest of the story is in the editorial; next, see T3.)

There are $N$ pillars in a row, and initially each pillar has damage $0$. Yuugi will perform $M$ attacks. Each attack is described by four parameters $l, r, s, e$: It means this attack affects all pillars from the $l$-th to the $r$-th (inclusive), dealing damage $s$ to the first pillar and $e$ to the last pillar within the range. The damage values form an arithmetic progression. For example, if $l = 1, r = 5, s = 2, e = 10$, then the damages to pillars $1 \sim 5$ are $2, 4, 6, 8, 10$ respectively. The oni need the final damage of each pillar after all attacks are completed.

The first line contains $2$ integers $N, M$, separated by a space; same below. Each of the next $M$ lines contains $4$ integers $l, r, s, e$, as described above. It is guaranteed that every individual damage applied to any pillar is an integer.

Because the output might be too large to print in full, to ensure you can indeed maintain all pillars’ damage, output two integers separated by a space: the XOR sum of all pillars’ final damages and the maximum of them. (The XOR sum is the value obtained by bitwise XOR over all numbers.) (The XOR operator in C++ is `^`.)

Sample explanation: Sample 1: Damage from the first attack: $2, 4, 6, 8, 10$. Damage from the second attack: $0, 1, 1, 1, 0$. Final damage of each pillar after all attacks: $2, 5, 7, 9, 10$. Output the XOR sum and the maximum, which are $3, 10$. Sample 2: The sixth pillar is not hit, so the answer remains unchanged. Constraints: This problem is worth $100$ points, split into $4$ subtasks. $(x/y)$ means (score/testcase count). - Fairy level $(18/3)$: $1 \le N, M \le 1000$. Even fairies playing around could finish this job, right? - Kappa level $(10/1)$: $s = e$. Can this replace my work? - Tengu level $(20/4)$: $1 \le N, M \le 10^5$. Small tricks no longer suffice. - Oni God level $(52/2)$: No special restrictions. Time to really think. These four parts of testdata do not overlap. For all data: $1 \le N \le 10^7$, $1 \le M \le 3 \times 10^5$, $1 \le l < r \le N$. All input, output, and pillar damage values are always within $[0, 9 \times 10^{18}]$. Tip: Due to various reasons, the time limit may be tight. C++ participants, please do not use `cin` for input. by orangebird. Translated by ChatGPT 5