CF1604B XOR Specia-LIS-t

CF传送门

题目大意：给定序列$a$,你可以把它分成若干份，对于每一部分，定义$h_k$为该部分序列的最长上升子序列，求是否存在一种分割序列$a$的方法，使$h_1,h_2...h_k$的异或和为0

本题容易被样例的分法误导，其实对于异或有一个很基础的性质，那就是偶数个1相异或结果为0
那很明显可以得到，如果$n$是偶数，那么每一个数为一个单独的部分，就有$h_1,h_2...h_n$都为1，$n$个1异或结果为0；如果$n$为奇数，那么显然我们只要构造出偶数个1就可以了，显然如果存在一个$a_i<=a_{i-1}$即可把这两个数捆绑在一起，它们的最长上升子序列仍为1，就构造出了偶数个1

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;

int t,n,a[N];

int main(){
	
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++) cin>>a[i];
		int flag=0;
		for(int i=1;i<=n;i++){
			if(i>1&&a[i]<=a[i-1]) flag=1;
		}
		if(flag==1||n%2==0) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}