又到了我最爱的一步都想不出来的环节了！
首先我们有一个分治做法：每次找出所有函数中 \(f_k(x_k) = \frac{L}{2}\) 的序列 \(\{x_k\}\)。我们按照这个进行排序，将函数分为两部分，这样我们就能把问题分为两个子问题：
- 定义域为 \([1, x_{\frac{n}{2}}]\)，值域为 \([1, \frac{L}{2}]\)；
- 定义域为 \([x_{\frac{n}{2}}, 10^{18}]\)，值域为 \([\frac{L}{2}, L]\)；
于是这个问题就可以分治解决了。每次找的过程需要二分，单次询问次数 \(O(n \log V)\)，总询问次数 \(O(n \log n \log V)\)，由于 \(\log V\) 是 \(60\)，所以询问次数超了，无法通过。
考虑优化。发现重点在于询问时我们每次都进行二分，非常慢。由于有 \(x_1 \le x_2 \Leftrightarrow f_1(x_2) \ge f_2(x_2)\)，所以我们实际上在求一个类似于中位数的东西。而众所周知求中位数有一个期望 \(O(n)\) 的做法，我们可以用一模一样的方法来求。
具体来说，就是每次随机一个函数 \(f_k\)，二分找出 \(x_k\)，然后按照 \(f_i(x_k)\) 的大小关系划分成两个集合，看两个集合的大小关系。如果哪边多就递归去划分哪个集合。这样找中位数，单次期望询问 \(O(n + \log n \log V)\) 次。套上分治，就是 \(O(n \log n + n \log V)\)，可以通过。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
long long l;
long long query(int k, long long x) {
printf("? %d %lld\n", k, x);
fflush(stdout);
long long v; scanf("%lld", &v);
return v;
}
long long find(int k, long long v, long long l, long long r) {
while (l < r) {
long long mid = (l + r) >> 1;
long long val = query(k, mid);
if (val < v) l = mid + 1;
else if (val > v) r = mid - 1;
else return mid;
}
return l;
}
mt19937 Rand(chrono::system_clock::now().time_since_epoch().count());
long long split(vector<int> s, long long v, int cnt, long long l, long long r,
vector<int> &x, vector<int> &y) {
int k = s[Rand() % s.size()];
long long p = find(k, v, l, r);
vector<int> X, Y, P = { k };
for (auto i : s) if (i != k) {
long long val = query(i, p);
if (val > v) X.push_back(i);
if (val < v) Y.push_back(i);
if (val == v) P.push_back(i);
}
while (X.size() < cnt && P.size()) X.push_back(P.back()), P.pop_back();
while (P.size()) Y.push_back(P.back()), P.pop_back();
if (X.size() == cnt) {
for (int i : X)
x.push_back(i);
for (int i : Y)
y.push_back(i);
return p;
}
if (X.size() > cnt) {
for (int i : Y)
y.push_back(i);
return split(X, v, cnt, l, r, x, y);
} else {
for (int i : X)
x.push_back(i);
return split(Y, v, cnt - X.size(), l, r, x, y);
}
}
long long ansl[MAXN], ansr[MAXN];
void solve(vector<int> s, long long l, long long r, long long vl, long long vr) {
if (s.size() == 0) return;
if (s.size() == 1) {
ansl[s[0]] = l, ansr[s[0]] = r;
return;
}
int m = s.size();
long long d = (vr - vl) / m;
long long v = vl + d * (m >> 1);
vector<int> x, y;
long long mid = split(s, v, m >> 1, l, r, x, y);
solve(x, l, mid, vl, v), solve(y, mid, r, v, vr);
}
int main() {
scanf("%d%lld", &n, &l);
vector<int> s;
for (int i = 1; i <= n; i++)
s.push_back(i);
solve(s, 0, 1000000000000000000, 0, l);
printf("!\n");
for (int i = 1; i <= n; i++) {
printf("%lld %lld\n", ansl[i], ansr[i]);
}
return 0;
}