[图解]CF2226D-Reserved Reversals

题目链接

https://codeforces.com/contest/2226/problem/D

题目大意

给定序列a，在a[l,r]的子序列，若其中最大值和最小值奇偶性不同，则可以颠倒这个子序列。问可否通过这样的操作使得a整体变为不下降序列。

核心观察

1. 任意相邻的一奇一偶可以随意交换
2. 如果把a所有的奇数提取出来构成奇数列，把所有偶数提取出来构成偶数列。若奇数列和偶数列能各自在内部排好序，再结合1的规则，a可以整体变为不下降序列。
3. 由2知，我们对于原始a序列，只要把奇/偶数列内部的所有逆序对调换完顺序就可。
   处理逆序对(a,b)(a>b)，有这样的结论：如果在整个a序列里任意位置存在z，z与ab奇偶性不同，有z>a或z<b，则逆序对(a,b)可以变为(b,a,z)/(z,a,b)，即为排好序的状态。

图解核心观察3

• 黑白表示奇偶性不同，无所谓谁奇谁偶
• 一旦出现逆序对，立马处理，所以图中ab之间全为黑
  
  
  
  
  

反思

只注意到了奇偶相邻可以随便换，没有注意到可以拆为奇数列和偶数列单独考虑，更想不到只要整个a中存在z就可以换逆序对，还得练。

提交后AC代码

https://codeforces.com/contest/2226/submission/373257695