E2. Salyg1n and Array (hard version) Codeforces Round 897 (Div. 2)

Problem - E2 - Codeforces

题目大意：有一个隐藏的长度为n的数组a，给出一个整数k，可以询问i，评测机返回[i,i+k-1]区间内的数的异或和，并将这一区间内的数的顺序翻转，要求在57次询问内得到整个数组的异或和

1<=k<=n<=k*k<=2500；n，k都是偶数

思路：因为询问一个区间后，这个区间会进行翻转，所以如果我们询问两个相邻的重合区间，那么区间重合部分被异或了两遍也就相当于没异或，其余两端的数都异或了一遍，然后这个重合区间又被反转到了最后，如果再以这个重合区间的左端点作为询问区间的左端点，那么这个重合区间的数都被异或了3遍，也就是异或了一遍，其他数也是一遍，这样就求出了这一段数的异或和，也就是我们可以用三次询问求出一段数量为(k,2k)的区间的异或和

拿k=6，n=10举例，初始询问[1,6]，数组变为[a[6],a[5],a[4],a[3],a[2],a[1],a[7],a[8],a[9],a[10]]，接着因为还剩两次操作和4个数没查，所以我们询问1+(n%k)/2，即[3,8]，数组变为[a[6],a[5],a[8],a[7],a[1],a[2],a[3],a[4],a[9],a[10]]，最后再询问1+n%k，即[5,10]，期间，这样我们a[1]~a[4]询问了三遍，其余的询问了1遍，异或起来都是一次贡献，即求得了a[1]~a[10]的异或和

我们知道了(k,2k)的区间怎么求，其他的区间直接永不重合的长度为k的区间去求即可，总询问次数不超过53次

//#include<__msvc_all_public_headers.hpp>
#include
using namespace std;
const int N = 3e4 + 5;
typedef long long ll;
int n;
void solve()
{
	int k;
	cin >> n >> k;
	ll ans = 0;
	for (int i = 1; i + k - 1 <= n; i += k)
	{//询问不重合的区间
		cout << "? " << i << endl;
		cout.flush();
		ll x;
		cin >> x;
		ans ^= x;
	}
	if (n % k)
	{//必须要有重合区间
		cout << "? " << n - k - (n % k) / 2 + 1 << endl;
		cout.flush();
		ll x;
		cin >> x;
		ans ^= x;
		cout << "? " << n - k + 1 << endl;
		cout.flush();
		cin >> x;
		ans ^= x;
	}
	cout << "! " << ans << endl;
	cout.flush();
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}