A. AquaMoon and Strange Sort
叉人题
如果数字各不相同，只需要统计每个数参与构成的逆序对总数，如果是奇数一定最终朝左，偶数朝右。无意义的数字交换对方向是没有影响的
继续考虑相同数字带来的影响。逆序对考虑的交换次数是最小交换，是保守排序，相同数字的相对位置不变。把交换次数的序列按奇偶提取出来，比如001110 001100。每次操作交换两个数字然后把它翻转，那么只有对相同的相邻数进行操作才有意义。
模型转化为给一个01序列，每次选择两个相邻的相同数，把它们翻转，问最后能否化成全0序列。
100100也是可行的。100100->111111->000000
把序列想象成多个连续的01段拼接。偶数段是可以任意转化的，对答案不产生影响，能把左右直接相连。奇数段则不行，需要把它压成一个数。用栈来考虑这个问题，如果是偶数段，什么也不插入，如果是奇数段，会插入一个0/1，如果栈尾和新插入的元素相同，说明能合并，如果不同就推进栈尾。在最终的栈中，如果栈空或者只有一个0，则合法，其他情况我们处理不掉1，均不合法。
1 #include <vector> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define ll long long 6 using namespace std; 7 const int maxn=1e5, N1=maxn+5; 8 9 template <typename _T> void read(_T &ret) 10 { 11 ret=0; _T fh=1; char c=getchar(); 12 while(c<‘0‘||c>‘9‘){ if(c==‘-‘) fh=-1; c=getchar(); } 13 while(c>=‘0‘&&c<=‘9‘){ ret=ret*10+c-‘0‘; c=getchar(); } 14 ret=ret*fh; 15 } 16 17 int n,T,ma; 18 int a[N1],num[N1]; 19 vector<int>to[N1]; 20 int stk[N1],tp; 21 22 struct BIT{ 23 int sum[N1]; 24 void upd(int x,int w){ for(int i=x;i<=ma;i+=i&(-i)) sum[i]+=w; } 25 int query(int x){ int ans=0; for(int i=x;i;i-=i&(-i)) ans+=sum[i]; return ans; } 26 void clr(){ for(int i=0;i<=ma;i++) sum[i]=0; } 27 }s; 28 29 int main() 30 { 31 // freopen("a.in","r",stdin); 32 scanf("%d",&T); 33 while(T--){ 34 35 scanf("%d",&n); ma=0; 36 for(int i=1;i<=n;i++) read(a[i]), ma=max(a[i],ma); 37 for(int i=1;i<=n;i++) 38 { 39 num[i]=s.query(ma)-s.query(a[i]); 40 s.upd(a[i],1); 41 } 42 s.clr(); 43 for(int i=n;i>=1;i--) 44 { 45 num[i]+=s.query(a[i]-1); 46 s.upd(a[i],1); 47 to[a[i]].push_back(num[i]&1); 48 } 49 s.clr(); 50 int fl=1; 51 for(int k=1;k<=ma;k++) 52 { 53 tp=0; 54 for(int i=0,j;i<to[k].size();) 55 { 56 for(j=i;j<to[k].size() && to[k][j]==to[k][i];j++); 57 if((j-i)&1) 58 { 59 if(!tp) stk[++tp]=to[k][i]; 60 else if(stk[tp]==to[k][i]) tp--; 61 else stk[++tp]=to[k][i]; 62 } 63 i=j; 64 } 65 if(tp>1||(tp==1&&stk[tp]==1)) fl=0; 66 to[k].clear(); tp=0; 67 } 68 puts(fl?"YES":"NO"); 69 70 } 71 return 0; 72 }