[Ynoi Easy Round 2022] 超人机械 TEST_95

给定一个序列 $a$ ，我们定义一个二元组 $(i,j)$ 为一个逆序对当且仅当 $i<j$ 且 $a_i>a_j$ 。定义两个逆序对 $(i_1,j_1),(i_2,j_2)$ **本质不同** 当且仅当 $a_{i_1}\ne a_{i_2}$ 或 $a_{j_1}\ne a_{j_2}$ 。 现在给出 $a$ 序列，问本质不同逆序对个数。 这还不够。 现在有 $q$ 组修改，每一次修改形如 $x~y$ 表示修改 $a_x$ 为 $y$ ，每一次修改 **不互相独立** ，即这一次修改会影响到后面的所有修改。 你需要对于每一次修改输出序列本质不同逆序对个数。 为了体现本题的不同解法，本题不同测试点拥有不同的时空限制。 ## Input 第一行一个整数 $n$ ，表示序列长度。 第二行 $n$ 个整数 $a_i$ ，表示序列 $a$ 。 第三行一个整数 $q$ ，表示询问组数。 后面 $q$ 行每行两个整数表示一次修改。 ## Output 一行一个整数，表示初始序列中本质不同逆序对个数。 后面 $q$ 行每行一个整数，第 $i + 1$ 行表示第 $i$ 次修改后序列本质不同逆序对个数。 [samples] ## Background 距今 300 年前，史前科学文明跨越了界限。出现了凌驾人类的人工智能，也就是超人机械。 不为人知的诞生，等察觉到时，世界已经在【他】的手中了。 究竟他身在何处，有什么样的外貌，虽然直到最后都没有人知道。但他好像可以出现在任何地方，化为任何样貌。 既非敌对，也非压制，单纯只是力量上占上风而已。也不太常出手进行干涉。我想一定是人类对他来说无所谓吧。 但即使如此，他还是会帮人实现愿望，魔人或魔龙，各式各样的不可思议，都是有人追求才被造出来的。  ...... 然而在某一天，超人机械消失了。 被腐铁菌干掉了，只是躲了起来，启程前往次元的另一端等，众说纷纭。留下的只有超人机械莫名其妙的发明品。和被世人自己弄得一团乱的世界。 这座树海一定也是超人机械的产物。魔力会一下子增幅，一下子又消耗掉对吧？魔法是从异次元将力量取出的能力，是超出人类理解范围的技术。 ## Note Idea：DPair，Solution：DPair，Code：DPair，Data：DPair 对于 $100\%$ 的数据 $1\le n \le 10^5, 0\le q \le 10^5, 1\le a_i, x, y \le n$ 。 以下为子任务：（留空部分表示无特殊限制） | 测试点编号 | $n$ | $q$ | $a_i,y$ | 特殊性质 | 时空限制 | 对应大样例 | | ---------- | --------- | --------- | ------- | -------- | -------- | ---------- | | 1-3 | $\le2000$ | $\le2000$ | | A | 1s/500MB | Sample1 | | 4-5 | | $=0$ | | A | 1s/50MB | Sample2 | | 6-10 | | | | A | 3s/500MB | Sample3 | | 11-15 | | | | | 3s/500MB | | | 16-20 | | | | | 1s/50MB | | 特殊性质 A：保证数据完全随机