题解：CF2178E Flatten or Concatenate

这场最喜欢的题。

观察一下样例，我们可以看出以下性质。

在序列 $a$ 中总存在两段子数组 $a[1,k],a[k,n]$ 使得他们的数组和相等。

同时，对于两个子数组同样存在上述性质，而且这是递归的。

然后就简单了，考虑一下二分一个点，使得找到当前的数组满足上述性质的子数组。

两个子数组中，长度短的一定存在最大值。

所以，二分套二分。$O(\log^2n)$，对于 $1\le n\le 1\times 10^5$ 和最大询问数为 $300$ 是可接受的。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		int low = 1, high = n;
		while (low < high) {
			cout << "? " << low << " " << high << endl;
			ll sum;
			cin >> sum;
			int l = low, r = high - 1, pos = -1;
			while (l <= r) {
				int mid = (l + r) >> 1;
				cout << "? " << low << " " << mid << endl;
				ll lsum;
				cin >> lsum;
				if (lsum * 2 == sum) {
					pos = mid;
					break;
				}
				if (lsum * 2 < sum)
					l = mid + 1;
				else
					r = mid - 1;
			}
			if (pos - low + 1 <= high - pos)
				high = pos;
			else
				low = pos + 1;
		}
		cout << "? " << low << " " << low << endl;
		ll ans;
		cin >> ans;
		cout << "! " << ans << endl;
	}
	return 0;
}

:::