首页 > 逆序对
开通博客写题解
头像 Kur1su
发表于 2021-06-07 11:32:38
Solution 先统计出原序列的逆序对，这部分可以用树状数组/归并排序完成。随后我们只关心逆序对的奇偶性。对于三种操作分别考虑：操作1，交换两个数字，逆序对的奇偶性改变。操作2，翻转序列，设当前的逆序对为 , 翻转后为 ，长度为 ， 考虑到翻转前后序列的逆序对满足 ，如果 是偶数，必为两奇或两偶 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 熠丶
发表于 2021-06-05 22:17:25
做法 任意交换两个数后，逆序对数的奇偶性改变 先求出原始序列的逆序对数的奇偶性(可以通过归并排序或者树状数组的方法求逆序对数) 对于操作1==>交换1次(l与r不相等)对于操作2==>对半交换对于操作3==>依次向左（或向右）逐位交换 代码 #include <iostr 展开全文
去ta的博客 赞 (0) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”