[??记录]AT4363 [ARC102D] Revenge of BBuBBBlesort!
command_block
2021-05-03 20:41:01
**记录** ： 给定长度为 $n$ 的排列 $p$ , 可以进行任意次如下操作，判定最终能否将其排成升序。
- 选择 $i$ 使得 $ 2 \leq i \leq n-1$ 且 $p_{i-1}>p_i>p_{i+1}$. 交换 $p_{i-1},p_{i+1}$.
$n\leq 3\times 10^5$ ，时限$\texttt{2s}$。
------------
某次操作完成后，从 $p_{i-1}>p_i>p_{i+1}$ 变为 $p_{i-1}<p_i<p_{i+1}$。
整个序列的逆序对个数减少了 $3$ 个。
又能发现，奇偶性不同的位置无法互相移动，故要将奇偶分别取出，判定是否都为 奇数/偶数。
又能发现，每次操作中，奇数部分**或**偶数部分的逆序对减少 $1$。
这得出一个必要条件 ： 奇数部分和偶数部分的逆序对的和是整个排列的逆序对的 $1/3$。
下面证明上述条件同时也是充分的。
记整个排列的逆序对个数为 $c_0$ ，奇数部分得逆序对个数为 $c_1$ ，偶数部分的逆序对个数为 $c_2$ 。
对奇数部分和偶数部分进行冒泡排序，共有 $c_1+c_2$ 次交换。
这些交换完成后，整个序列都是有序的，故逆序对个数减少了 $c_0$。
每次操作中逆序对个数至多减少 $3$ ，由于 $c_0=3(c_1+c_2)$ ，故每次操作中逆序对个数的减少量都达到上界，也都满足操作所需的条件。
需要求逆序对，复杂度为 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 300500
using namespace std;
#define lbit(p) (p&-p)
int n,t[MaxN];
void add(int p)
{while(p<=n){t[p]++;p+=lbit(p);}}
int qry(int p){
int ret=0;
while(p){ret+=t[p];p^=lbit(p);}
return ret;
}
int p[MaxN];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&p[i]);
if ((p[i]&1)!=(i&1)){puts("No");return 0;}
}
ll c0=0,c1=0,c2=0;
for (int i=1;i<=n;i++){
add(p[i]);
c0+=i-qry(p[i]);
}
for (int i=1;i<=n;i++)t[i]=0;
for (int i=1;i<=n;i+=2){
add(p[i]);
c1+=(i+1)/2-qry(p[i]);
}
for (int i=1;i<=n;i++)t[i]=0;
for (int i=2;i<=n;i+=2){
add(p[i]);
c2+=i/2-qry(p[i]);
}
puts(3*(c1+c2)==c0 ? "Yes" : "No");
return 0;
}
```