cf1322BPresent(基数排序+双指针+拆位)

cf1322BPresent
首先拆位是显然的，对于两个数a[i],a[j]，除了考虑当前位上的数，我们还要考虑是否会产生进位，我们可以利用基数排序+双指针，因为我们每次都是将低位的排好序了，所以我们可以用双指针计算进位，然后分类计算一下，当前为为1的情况即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<ctime>
#include<unordered_map>
#include<queue>
#define A puts("YES")
#define B puts("NO")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
#define bit ((a[i]>>id)&1)
using namespace std;
//typedef __int128 i128;
typedef double db;
typedef long long ll;
const ll mo=1e9+7;
const int N=4e5+5;
int b[31],n,a[N],c[N],cnt[2],now,ans;
int t[N][2];
int s1,s2;
bool pd(int x,int y,int d){
	s1=x&(b[d]-1);
	s2=y&(b[d]-1);
	return s1+s2>=b[d];
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);

	b[0]=1;
	fo(i,1,30) b[i]=b[i-1]*2;
	
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]);
	
	fo(id,0,30) {
		now=0;
		
		memset(cnt,0,sizeof(cnt));
		memset(t,0,sizeof(t));
		
		fo(i,1,n) cnt[bit]++; 
		
		if (!id) {
			now+=(cnt[0]&1)*(cnt[1]&1);
		}
		else{
			
			fd(i,n,1) {
				fo(j,0,1) t[i][j]=t[i+1][j];
				t[i][bit]++;
			}
			
			int r=n;
			fo(i,1,n-1) {
				
				r=max(i+1,r);
				while (r>i+1 && pd(a[r-1],a[i],id)) r--;
				if (pd(a[r],a[i],id)) {
					now+=t[r][bit];
					now+=t[i+1][bit^1]-t[r][bit^1];
				}
				else {
					now+=t[i+1][bit^1];
				}
				now&=1;
			}
			
		}
		
		cnt[1]+=cnt[0];
		fd(i,n,1) c[cnt[bit]--]=a[i];
		fo(i,1,n) a[i]=c[i];
		if (now&1) ans+=b[id];
	}
	
	printf("%d",ans);
	
	return 0;
}