[ARC092B] Two Sequences

细节超多，开始找不到任何数据结构维护。

考虑比较暴力的做法。

对答案每一位分别考虑，设当前考虑到第 i i i 位。

计算所有数模 2 i + 1 2^{i + 1} 2i+1 的余数，并升序排序使其满足单调性。(以下都按余数讨论)

若对于一个数 a a a，有数 b b b 满足 ( a + b )   m o d   2 i + 1 ≥ 2 i (a+b)bmod 2^{i+1}geq 2^i (a+b)mod2i+1≥2i，则 a , b a,b a,b 原数之和第 i i i 位为 1 1 1。

那么对于每个 a i a_i ai​ 分类讨论：

• 若 a i ≤ 2 i − 1 a_i le 2^{i-1} ai​≤2i−1，则答案在 [ 2 i − a , 2 i + 1 − a − 1 ] [2^i-a,2^{i+1}-a-1] [2i−a,2i+1−a−1] 范围内，二分统计个数即可。
• 否则即 a i > 2 i − 1 a_i>2^{i-1} ai​>2i−1，则答案在 [ 0 , 2 i + 1 − a − 1 ] ∪ [ 2 i + 1 + 2 i − a , 2 i + 1 − 1 ] [0,2^{i+1}-a-1] cup [2^{i+1}+2^i-a,2^{i+1}-1] [0,2i+1−a−1]∪[2i+1+2i−a,2i+1−1] 范围内，二分统计个数即可（两区间不交）。

对于每一位的总个数判断奇偶性添加贡献即可。

时间复杂度 O ( n log ⁡ n log ⁡ V ) mathcal O(nlog nlog V) O(nlognlogV)。

#include

using namespace std;

#define int long long
typedef long long ll;

#define ha putchar(' ')
#define he putchar('n')

inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return x * f;
}

inline void write(int x)
{
	if(x < 0)
	{
		putchar('-');
		x = -x;
	}
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + 48);
}

const int _ = 2e5 + 10;

int n, a[_], b[_], c[_], d[_], ans;

signed main()
{
	//	a[1] = 1, a[2] = 2;
	//	cout << upper_bound(a + 1, a + 2 + 1, 3) - a;
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 1; i <= n; ++i) b[i] = read();
	for(int x = 30; x >= 0; --x)
	{
		int nw = 1 << x, t = 0;
		for(int i = 1; i <= n; ++i) c[i] = a[i] % (nw << 1);
		for(int i = 1; i <= n; ++i) d[i] = b[i] % (nw << 1);
		sort(c + 1, c + n + 1), sort(d + 1, d + n + 1);
		for(int i = 1; i <= n; ++i)
		{
			if(c[i] <= nw)
			{
				// [2^i-a,2^{i+1}-a-1]
				int ps1 = upper_bound(d + 1, d + n + 1, (nw << 1) - c[i] - 1) - d - 1;
				int ps2 = lower_bound(d + 1, d + n + 1, nw - c[i]) - d - 1;
				t += ps1 - ps2;
			}
			else
			{
				// [2^{i+1}+2^i-a,2^{i+1}-1]
				// [0,2^{i+1}-a-1]
				int ps1 = upper_bound(d + 1, d + n + 1, (nw << 1) - 1) - d - 1;
				int ps2 = lower_bound(d + 1, d + n + 1, (nw << 1) + nw - c[i]) - d - 1;
				t += ps1 - ps2;
				ps1 = upper_bound(d + 1, d + n + 1, (nw << 1) - c[i] - 1) - d - 1;
				ps2 = lower_bound(d + 1, d + n + 1, 0) - d - 1;
				t += ps1 - ps2;
			}
		}
		//		cout << nw << ": " << t <<"n";
		if(t & 1) ans |= nw;
	}
	write(ans), he;
	return 0;
}