当我只是水结论敲个板子吧...下次不开这么没意思的题目..
必要性证明完了就可以过,有些题解证明不是很懂.那就按必要性水一发吧.
#include <bits/stdc++.h> using namespace std; const int N=3e5+4; long long odd=0,even=0,tot=0,sum[3][N]; int n; int lowbit(int x) { return x&(-x); } void add(int pos,int val,int op) { while(pos<=n) { sum[op][pos]+=val; pos+=lowbit(pos); } } long long query(int pos,int op) { long long res=0; while(pos) { res+=sum[op][pos]; pos-=lowbit(pos); }return res; } int main() { bool flag=true; int x; scanf("%d",&n); for(long long i=1;i<=n;i++) { scanf("%d",&x); if(x&1) { odd+=query(n,1)-query(x,1); tot+=query(n,0)-query(x,0); add(x,1,1); add(x,1,0); } else { even+=query(n,2)-query(x,2); tot+=query(n,0)-query(x,0); add(x,1,2); add(x,1,0); } if(x%2!=i%2) flag=false; } if((even*3+odd*3)!=tot) flag=false; if(tot%3!=0) flag=false; if(flag) puts("Yes"); else puts("No"); return 0; }
下次写这题,好像很难的样子,https://www.luogu.com.cn/problem/AT2274 那咋先去回刷一下kuangbin.