题头
You are given a permutation of 1,2,…,N: p1,p2,…,pN. Determine if the state where pi=i for every i can be reached by performing the following operation any number of times:
Choose three elements pi−1,pi,pi+1 (2≤i≤N−1) such that pi−1>pi>pi+1 and reverse the order of these three.
Constraints
3≤N≤3×105
p1,p2,…,pN is a permutation of 1,2,…,N.
Input
Input is given from Standard Input in the following format:
N
p1
:
pN
Output
If the state where pi=i for every i can be reached by performing the operation, print Yes; otherwise, print No.
Sample Input 1
5
5
2
1
4
3
Sample Output 1
Yes
The state where pi=i for every i can be reached as follows:
Reverse the order of p1,p2,p3. The sequence p becomes 1,2,5,4,3.
Reverse the order of p3,p4,p5. The sequence p becomes 1,2,3,4,5.
Sample Input 2
4
3
2
4
1
Sample Output 2
No
Sample Input 3
7
3
2
1
6
5
4
7
Sample Output 3
Yes
Sample Input 4
6
5
3
4
1
2
6
Sample Output 4
No
大意：给你N个数字，每个数字分别为1~N中的一个数，然后你可以将如果第i个数a[i]满足a[i]>a[i+1]>a[i+2],你可以将a[i]和a[i+2]交换，问是否能使所有的数i位于第i位上；
暴力做法就是直接如果还有可以交换的就一直跑，最后检查一下，复杂度会被卡到的，
不过看到有个人直接跑1200次，结果A了，心里复杂万分。。 。。数据太水了，换我让他分分钟wa完
（1）对于任意一个数，如果它已经在它应该在的位置了，那它无论如何也不能被交换，否则它就回不到原来的位置了，
（2）同样对于任意一个作为两边交换时的“桥梁“的那个数，如果它不在自己应该在的位置，那么就不能它两边的数，因为如果你两边的数交换了，那你这个数就无法被和两边交换了
（3） 奇数位的数只能是奇数，偶数位的数只能是偶数，因为每次交换都是+2来着
如果一个点被交换了，那么剩下所有交换就只有可能在它的“桥梁”的左边或者右边进行
然后如果我们从最左边开始，那所有交换都只有可能在现在点的右边进行
也就是说整个数列最多只会被遍历一遍，总复杂度O(n)；
还有就是可以证明交换顺序不会影响答案
这样我们就可以求出对于每一个点最多可以被交换到的地方，然后看满不满足条件
大概就是这样了吧
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int a[300005],n;
inline bool check(int l,int r)//判断点i能否跑到自己应该在的位置
{
int mn=n+1,mx=0;
for(int i=l;i<=r;i++) mn=min(mn,a[i]),mx=max(mx,a[i]);
if(mn!=l||mx!=r) return 0;//如果i和r不能在这个范围内找到自己的位置
int x=0,y=0;
for(int i=l;i<=r;i+=2)//判断能不能交换的过去，这可以手推一下
{
if(x<a[i]&&y<a[i]) y=a[i];
else if(x<a[i]) x=a[i];
else return 0;
}
return 1;
}
int main(){
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
}
for(int i=1;i<=n;i++)
{
if((a[i]&1)!=(i&1)){cout<<"No";return 0;}//(3)
}
for(int i=1;i<=n-2;i++)
{
if(a[i]==i) continue;
int k=i;
while(k<=n-2)//找点i能换到的地方
{
if(a[k+1]!=k+1) break;//(2)
if(a[k+2]==k+2) break;//(1)
k+=2;
}
if(!check(i,k)){cout<<"No";return 0;//检查i在能到达的区间里是否能找到自己的正确位置
i=k;
}
cout<<"Yes";
return 0;
}
然后我还想到一种算法
因为如果一个点被交换了，那么剩下所有交换就只有可能在它的“桥梁”的左边或者右边进行
所以我们最多交换n次，然后用堆维护在O()时间内找出能交换的点；
总复杂度O(nlogn) 也是挺不错的，然而并没有写这种方法；