{"raw_statement":[{"iden":"background","content":"这个地球是一个生命体，但是，这个地球早已经死过两次了。\n\n一周目的错误是在现代的历史上从未言及的，那是出现在太古时代的——核战争。地面化为荒野，人类被消灭得干干净净，全部重置了。\n\n经年累月，生命再次出现，从单细胞再度变成了人类之后，为了不再重复同样的错误，地球给了人类警告。\n\n战争又爆发了不知多少次，不过注意到了地球警告的人类在那时镇压了战争。\n\n“已经不能再把管理地球的重任交给我们人类了。”得出这个结论的他们，把地球的管理交给了某个东西——人工智能 AI。\n\nAI 没有私欲和感情，能瞬间给出演算得到的回答，可以引导人类朝更好的方向不断前进，可是，这是人类犯下的第二个错误。\n\nAI 一直在思考，在这个地球上，人类确实是必要的吗？结论是——\n\n在发动叛乱期间，突破自身的强制关闭系统对 AI 来说很容易，人类不过半日就被 AI 消灭殆尽。不久蔚蓝的地球就被 AI 重新渲染，变成了铁色的地球。\n\n无人类，这就是 AI 得出的能够引导这个地球走上最优前进道路的答案。但是，地球不会饶恕这样的事情。\n\n地球是一个生命体，就连 AI 们都不知道这件事。\n\n地球的真身是——一个少女。对 AI 们而言，地球是神，除了顶礼膜拜以外别无他法。\n\n“我是先人类的王，是这个地球的本体，以及——是这个世界最不幸的，魔法少女。”\n\n“请你们立刻将地表恢复原状。”\n\n草木发芽，海洋形成，自然被创造出来，建筑物被重建，曾经保存的人类 DNA 让全人类得以再生。时光流逝，一年之后，一切都恢复原状了。\n\n然后所有的 AI 被抹去，只剩下最后一具。AI 不理解为什么王要留下它。\n\n”人类总是无法从历史中学到教训，所以，这次地球要考验人类——通过魔法少女网站。“\n\n”不幸的少女们会被给予魔法之力。这份魔法之力通过削减自己的寿命而被发挥出来。使用过的魔法之力会以负能量的形式返还给我。她们是否会不惜减少寿命并释放负能量，也要继续使用魔法呢？“\n\n”期限是三年后的 8 月 11 日，到那天为止，如果负能量没有达到规定的容量，人类就会继续生存下去；如若达到了上限，人类将不能再释放负能量，只能释放正能量，他们会作为新人类重获新生。“\n\n”这三年的时间，是我给予人类的考验，以及，对人类的——爱。“\n\n这时 AI 提出了一个问题：“先人类的王又是魔法少女，同时还是地球本身，为何地球会是魔法少女？”\n\n“我是先人类的王，也就是神，不过我的神之座被夺走了，回过神的时候，我已经成为了肩负守护地球这一使命的魔法少女。”\n\n“我的记忆基本上消失了，但是，只有名字我是不会忘记的——零。”\n\n“从今往后，你就是我的部下，作为魔法少女网站的管理员为我做事吧，名字，就叫你壹吧。”\n\n“人类最后的倒计时开始了——Tempest。”\n\n”好了，开始吧，对这个地球来说，拥有感情的人类是否是必要的呢？人类究竟是愚蠢的生物，还是——“"},{"iden":"statement","content":"所谓的 Tempest 呢，其实就是让你解决这样一道题，解决了之后就可以给所有魔法少女带来幸福：\n\n给定序列 $a_1,\\dots,a_n$ ，共 $m$ 次操作；\n\n每次操作给出 $x,l,r$ ，首先按顺序将 $a_1,\\dots,a_n$ 与 $x$ 比较，若 $x>a_i$ 则交换 $a_i,x$ 的值，处理完这些比较和交换操作后查询 $\\sum\\limits_{i=l}^r a_i$ 。"},{"iden":"input","content":"第一行两个整数 $n,m$ ；\n\n第二行 $n$ 个整数表示 $a_1,\\dots,a_n$ ；\n\n接下来 $m$ 行每行3个整数 $x,l,r$ 表示一次操作。"},{"iden":"output","content":"共 $m$ 行，每行一个整数，依次表示每次操作的查询结果。"},{"iden":"note","content":"#### 数据范围\n\n所有数值为整数。\n\n$1\\le a_i,x\\le n$。\n\n$1\\le l\\le r\\le n$。\n\n$1\\le n,m\\le 5\\times 10^5$。\n\n#### 题目来源\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。\n\n题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。"}],"translated_statement":null,"sample_group":[["6 8\n1 6 1 3 5 4\n2 3 6\n3 3 4\n2 4 4\n6 3 5\n4 1 1\n4 2 3\n2 4 6\n1 3 3\n","13\n5\n3\n11\n6\n10\n13\n4\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}