CF 1732F Omkar and Modes_综合

题意

交互，告诉你一个不降的序列 $a$ 长度为 $n$ ，你可以使用若干次下面的询问：

询问 $l,r$ ，返回 $[l,r]$ 中的众数 $x$ 以及它的出现次数 $f$ 。如果有多个众数，返回最小的那个。

假设数列中有 $k$ 个不同的数字（ $k$ 不告诉你），你需要在 $4k$ 次询问中求出这个序列。 $n \le 200000$

题解

没看过官方标算，不知道自己的做法和标算一不一样……

考虑 $solve(l,r)$ 表示执行过之后就能求出 $[l,r]$ 中的所有数字。我们先询问一遍 $[l,r]$ ，得到当前的众数 $x$ 和它的出现次数 $f$ 。

我们考虑一件事，如果已知 $x,f$ ，并且已知了一个 $i$ 使得 $a_i=x$ ，那么我们就可以使用两次询问求出所有 $x$ 的具体位置。分别询问 $[i-f+1,i]$ 和 $[i,i+f-1]$ ， $x$ 必然在其中一个区间成为众数，这样就可以知道 $x$ 的开头位置或者结尾位置，连续的 $f$ 个就都是 $x$ 。然后扔掉这 $f$ 个数，递归两半继续进行即可。

于是现在问题落到了如何找到 $a_i=x$ 的任意 $i$ 。我们先考虑 $solve(1,n)$ 时怎么找，可以分别询问 $a_f,a_{2f},a_{3f},...$ 是多少，直到找到了 $x$ 。显然刚刚询问的这些数字都互不相同（否则 $x$ 就不是众数了），这样我们顺便得到了一些其他数字的某个出现位置。

这给了我们一个启发，即能不能做到每个数字都恰好被询问一次？答案是肯定的。

假设当前在 $solve(l,r)$ 中，如果当前众数 $x$ 的位置已经被以前找到过了，那么就不需要询问；否则的话，假设我们知道了 $a_{k_1},a_{k_2},...,a_{k_t}$ 的值（这些数字互不相同），那么我们就可以知道 $x$ 在哪两个数字之间。假设是 $a_p$ 和 $a_q$ ，那么我们从 $\max(l,p+f)$ 开始，每隔 $f$ 个数字问一次，直到问到 $x$ 为止。显然问出的这些数字仍然和以前的所有数字互不相同（首先， $[l,r]$ 和外部的数字互不相同；其次， $[l,r]$ 内部的数字每隔 $f$ 问一次也互不相同）。

综上，我们就用了 $k$ 次询问找到了每种数字的某个出现位置，每次递归时需要一次询问，此外每个数字找到它出现的整个区间需要两次询问。总询问次数刚好是 $4k$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<typename T> inline void chkmin(T &a, const T &b) { a = a < b ? a : b; }
template<typename T> inline void chkmax(T &a, const T &b) { a = a > b ? a : b; }const int MAXN = 200005;
int n, aa[MAXN], bb[MAXN];
map<int, int> mp;void ask(int l, int r, int &x, int &f) {printf("? %d %d\n", l, r);fflush(stdout);scanf("%d%d", &x, &f);
}void divide(int l, int r) {if (l > r) return;int x, f; ask(l, r, x, f);if (r - l + 1 == f) {for (int i = l; i <= r; i++) aa[i] = x;mp[x] = l;return;}auto p = mp.lower_bound(x);int pla = -1;if (p != mp.end() && p->first == x) pla = p->second;else {--p;for (int i = max(l, p->second + f);; i += f) {int a, b; ask(i, i, a, b);assert(!mp[a]);mp[a] = i;if (a == x) { pla = i; break; }}}int a, b, pl, pr; ask(max(l, pla - f + 1), pla, a, b);if (a == x) pl = pla - b + 1, pr = pla - b + f;else {ask(pla, min(pla + f - 1, r), a, b);pl = pla + b - f, pr = pla + b - 1;}for (int i = pl; i <= pr; i++) aa[i] = x;divide(l, pl - 1);divide(pr + 1, r);
}int main() {scanf("%d", &n);mp[0] = 0;divide(1, n);putchar('!');for (int i = 1; i <= n; i++)printf(" %d", aa[i]);fflush(stdout);return 0;
}