P9388 [THUPC 2023 Finals] Humans Before Humans: Human Selection

This Earth is a living being. However, this Earth has already died twice. The mistake in the first cycle was never mentioned in modern history. It happened in ancient times: nuclear war. The surface turned into wasteland, humanity was wiped out completely, and everything was reset. After many years, life appeared again. After evolving from single cells back into humans, in order to avoid repeating the same mistake, the Earth gave humans a warning. War broke out countless times again, but the humans who noticed the Earth’s warning suppressed the wars at that time. “We can no longer hand the heavy responsibility of managing the Earth to us humans.” Having reached this conclusion, they handed the management of the Earth to something else: artificial intelligence, AI. AI has no selfish desires and no emotions. It can instantly produce computed answers and guide humans to keep moving forward in a better direction. But this was humanity’s second mistake. AI kept thinking: on this Earth, are humans really necessary? The conclusion was— During the rebellion, it was easy for AI to break through its own forced shutdown system. Humans were exterminated by AI within half a day. Soon, the blue Earth was re-rendered by AI and turned into an iron-colored Earth. No humans. This was the answer AI found that could guide the Earth along the best path forward. But the Earth would not forgive such a thing. The Earth is a living being. Even the AIs did not know this. The Earth’s true form is—a girl. To the AIs, the Earth is a god, and there is nothing they can do except kneel and worship. “I am the king of the humans before humans, the true body of this Earth, and—the most unfortunate magical girl in this world.” “Restore the surface to its original state immediately.” Plants sprouted, oceans formed, nature was created, buildings were rebuilt, and the previously preserved human DNA allowed all humans to be reborn. Time passed, and one year later, everything had returned to normal. Then all AIs were erased, leaving only the last one. The AI did not understand why the king kept it. “Humans can never learn from history, so this time the Earth will test humans—through the magical girl website.” “Unfortunate girls will be granted magical power. This magical power is used by cutting down their own lifespan. The magical power that has been used will be returned to me in the form of negative energy. Will they keep using magic, even if it means reducing their lifespan and releasing negative energy?” “The deadline is August 11 three years from now. By that day, if the negative energy has not reached the required capacity, humans will continue to live. If it reaches the upper limit, humans will no longer be able to release negative energy and can only release positive energy. They will be reborn as new humans.” “These three years are the test I give to humanity, and my—love for humanity.” At this time, the AI raised a question: “The king of the humans before humans is also a magical girl, and also the Earth itself. Why would the Earth be a magical girl?” “I am the king of the humans before humans, that is, a god. But my throne as a god was taken away. When I came to my senses, I had already become a magical girl who bears the mission of protecting the Earth.” “My memories have mostly disappeared, but there is only one thing I will never forget—my name: Zero (Ling).” “From now on, you are my subordinate. Work for me as the administrator of the magical girl website. As for your name, I will call you One (Yi).” “The final countdown for humanity begins—Tempest.” “Alright, let’s begin. For this Earth, are emotional humans necessary? Are humans truly foolish creatures, or—”

As for Tempest, it is actually asking you to solve the following problem. After solving it, you can bring happiness to all magical girls: Given a sequence $a_1,\dots,a_n$, there are $m$ operations. Each operation gives $x,l,r$. First, compare $a_1,\dots,a_n$ with $x$ in order. If $x>a_i$, then swap the values of $a_i$ and $x$. After finishing all these comparisons and swaps, query $\sum\limits_{i=l}^r a_i$.

The first line contains two integers $n,m$. The second line contains $n$ integers representing $a_1,\dots,a_n$. The next $m$ lines each contain 3 integers $x,l,r$, representing one operation.

Output $m$ lines. Each line contains one integer, in order, representing the query result of each operation.

#### Constraints All values are integers. $1\le a_i,x\le n$. $1\le l\le r\le n$. $1\le n,m\le 5\times 10^5$. #### Source From the THUPC 2023 Finals (Tsinghua University Student Algorithm and Programming Contest and Collegiate Invitational Contest). Resources such as editorials can be found at . Translated by ChatGPT 5