[ARC092B] Two Sequences

[ARC092B] Two Sequences

细节超多,Started not finding any data structure maintenance.

Consider a more violent approach.

Consider each answer individually,Let the current take into account the first $i$ 位.

Calculate all numbers $2^{i+1}$ 的余数,And sort in ascending order to satisfy monotonicity.(The remainder is discussed below)

若对于一个数 $a$,有数 $b$ 满足 $(a+b)\mathrm{mod}{2}^{i+1}\ge 2^i$,则 $a,b$ The sum of the original numbers $i$ 位为 $1$.

那么对于每个 $a_i$ 分类讨论：

• 若 $a_i\le 2^{i-1}$,则答案在 $[2^i-a,2^{i+1}-a-1]$ 范围内,Binary statistics can be counted.
• 否则即 $a_i>2^{i-1}$,则答案在 $[0,2^{i+1}-a-1]\cup [2^{i+1}+2^i-a,2^{i+1}-1]$ 范围内,Binary statistics can be counted（The two intervals do not intersect）.

It is enough to add contribution to the judgment of parity for the total number of each bit.

时间复杂度 $\mathcal{O}(n\log n\log V)$.

#include<bits/stdc++.h>

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;
}

/* */