{"problem":{"name":"[Ynoi Easy Round 2022] 超人机械 TEST_95","description":{"content":"给定一个序列 $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$ 组修改，每一次修改","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":512000},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9068"},"statements":[{"statement_type":"Markdown","content":"给定一个序列 $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}$ 。\n\n现在给出 $a$ 序列，问本质不同逆序对个数。\n\n这还不够。\n\n现在有 $q$ 组修改，每一次修改形如 $x~y$ 表示修改 $a_x$ 为 $y$ ，每一次修改 **不互相独立** ，即这一次修改会影响到后面的所有修改。\n\n你需要对于每一次修改输出序列本质不同逆序对个数。\n\n为了体现本题的不同解法，本题不同测试点拥有不同的时空限制。\n\n## Input\n\n第一行一个整数 $n$ ，表示序列长度。\n\n第二行 $n$ 个整数 $a_i$ ，表示序列 $a$ 。\n\n第三行一个整数 $q$ ，表示询问组数。\n\n后面 $q$ 行每行两个整数表示一次修改。\n\n## Output\n\n一行一个整数，表示初始序列中本质不同逆序对个数。\n\n后面 $q$ 行每行一个整数，第 $i + 1$ 行表示第 $i$ 次修改后序列本质不同逆序对个数。\n\n[samples]\n\n## Background\n\n距今 300 年前，史前科学文明跨越了界限。出现了凌驾人类的人工智能，也就是超人机械。\n\n不为人知的诞生，等察觉到时，世界已经在【他】的手中了。\n\n究竟他身在何处，有什么样的外貌，虽然直到最后都没有人知道。但他好像可以出现在任何地方，化为任何样貌。\n\n既非敌对，也非压制，单纯只是力量上占上风而已。也不太常出手进行干涉。我想一定是人类对他来说无所谓吧。\n\n但即使如此，他还是会帮人实现愿望，魔人或魔龙，各式各样的不可思议，都是有人追求才被造出来的。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/qmrcnbwc.png)\n\n......\n\n然而在某一天，超人机械消失了。\n\n被腐铁菌干掉了，只是躲了起来，启程前往次元的另一端等，众说纷纭。留下的只有超人机械莫名其妙的发明品。和被世人自己弄得一团乱的世界。\n\n这座树海一定也是超人机械的产物。魔力会一下子增幅，一下子又消耗掉对吧？魔法是从异次元将力量取出的能力，是超出人类理解范围的技术。\n\n## Note\n\nIdea：DPair，Solution：DPair，Code：DPair，Data：DPair\n\n对于 $100\\%$ 的数据 $1\\le n \\le 10^5, 0\\le q \\le 10^5, 1\\le a_i, x, y \\le n$ 。\n\n以下为子任务：（留空部分表示无特殊限制）\n\n| 测试点编号 | $n$       | $q$       | $a_i,y$ | 特殊性质 | 时空限制 | 对应大样例 |\n| ---------- | --------- | --------- | ------- | -------- | -------- | ---------- |\n| 1-3        | $\\le2000$ | $\\le2000$ |         | A        | 1s/500MB | Sample1    |\n| 4-5        |           | $=0$      |         | A        | 1s/50MB  | Sample2    |\n| 6-10       |           |           |         | A        | 3s/500MB | Sample3    |\n| 11-15      |           |           |         |          | 3s/500MB |            |\n| 16-20      |           |           |         |          | 1s/50MB  |            |\n\n特殊性质 A：保证数据完全随机","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9068","tags":["2022","O2优化","Ynoi"],"sample_group":[["5\n3 1 2 1 5 \n1\n3 3","3\n1"],["6\n1 1 4 5 1 4\n3\n1 5\n1 1\n4 4","3\n3\n3\n1"],["15\n6 14 12 12 6 8 9 3 8 14 14 15 6 15 2 \n10\n12 13\n10 10\n14 9\n8 8\n11 11\n5 8\n1 6\n11 12\n2 13\n1 9","23\n25\n29\n30\n24\n29\n29\n29\n24\n20\n20"]],"created_at":"2026-03-03 11:09:25"}}