A5677. 「THUPC 2023」先人类的人类选别
编程题
省选/NOI-
知识点
题目描述
所谓的 Tempest 呢，其实就是让你解决这样一道题，解决了之后就可以给所有魔法少女带来幸福：
给定序列 $a_1,\dots,a_n$ ，共 $m$ 次操作；
每次操作给出 $x,l,r$ ，首先按顺序将 $a_1,\dots,a_n$ 与 $x$ 比较，若 $x>a_i$ 则交换 $a_i,x$ 的值，处理完这些比较和交换操作后查询 $\sum\limits_{i=l}^r a_i$ 。
给定序列 $a_1,\dots,a_n$ ，共 $m$ 次操作；
每次操作给出 $x,l,r$ ，首先按顺序将 $a_1,\dots,a_n$ 与 $x$ 比较，若 $x>a_i$ 则交换 $a_i,x$ 的值，处理完这些比较和交换操作后查询 $\sum\limits_{i=l}^r a_i$ 。
输入格式
第一行两个整数 $n,m$ ；
第二行 $n$ 个整数表示 $a_1,\dots,a_n$ ；
接下来 $m$ 行每行3个整数 $x,l,r$ 表示一次操作。
第二行 $n$ 个整数表示 $a_1,\dots,a_n$ ；
接下来 $m$ 行每行3个整数 $x,l,r$ 表示一次操作。
输出格式
共 $m$ 行，每行一个整数，依次表示每次操作的查询结果。
输入输出样例
输入 #1
6 8 1 6 1 3 5 4 2 3 6 3 3 4 2 4 4 6 3 5 4 1 1 4 2 3 2 4 6 1 3 3
输出 #1
13 5 3 11 6 10 13 4
说明/提示
所有数值为整数
$1\le a_i,x\le n$。
$1\le l\le r\le n$。
$1\le n,m\le 5\times 10^5$。
$1\le a_i,x\le n$。
$1\le l\le r\le n$。
$1\le n,m\le 5\times 10^5$。