X or What?（2019 Google Kickstart Round D）

題目連結：https://codingcompetitions.withgoogle.com/kickstart/round/0000000000051061

異或的神奇性質。a^b，那麼實際上是b的二進制中為1的位置，會讓a中對應位置翻轉(0^1=1,1^1=0)，是以這題要求一個保證異或和的二進制的1的位數為偶數的最長子區間的長度，就可以用以上性質了，a^b，如果b的1的個數時偶數，那麼a的1的個數就會變化偶數個。

那麼我們找出1-n中有cnt個1為偶數個的數字，如果cnt%2==0，那麼1-n這個區間的異或和的二進制1的個數就是偶數。

如果cnt%2==1，那麼就必須舍棄一個二進制中1的個數為奇數的數字，那麼我們找出這些數字中最左邊和最右邊的l和r，ans=max(n-l,r-1)。

#include<bits/stdc++.h>
#define maxl 300010

using namespace std;

int n,q,ans,cas,sum;
int a[maxl],num[maxl];
set <int> s;
set <int> :: iterator it;

inline int getnum(int x)
{
	int cnt=0;
	while(x>0)
	{
		if(x&1)
			cnt++;
		x>>=1;
	}
	return cnt;
}

inline void prework()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	s.clear();sum=0;
	for(int i=1;i<=n;i++)
	if(num[a[i]]%2==1)
	{
		sum++;
		s.insert(i);
	}
} 


inline void mainwork()
{
	printf("Case #%d:",cas);
	int p,x,id1,id2; 
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&p,&x);
		if(num[a[p+1]]%2==1)
		{
			it=s.lower_bound(p+1);
			s.erase(it);
			sum--;
		}
		a[p+1]=x;
		if(num[a[p+1]]%2==1)
		{
			s.insert(p+1);
			sum++;
		}
		if(sum%2==0)
			ans=n;
		else
		{
			it=s.begin();
			id1=(*it);
			it=s.end();--it;
			id2=(*it);
			ans=max(n-id1,id2-1);
		}
		printf(" %d",ans);
	} 
}

inline void print()
{
	puts("");
}

int main()
{
	//freopen("C.in","r",stdin);
	for(int i=0;i<=1024;i++)
		num[i]=getnum(i);
	int t;
	scanf("%d",&t);
	for(cas=1;cas<=t;cas++)
	{ 
		prework();
		mainwork();
		print();
	}
	return 0;
}