可以把限制看成 \(0.75n^2\)。发现 \(0.75n^2 = 0.5n^2 + 2 \times 0.5 (\frac{n}{2})^2\)。这启发我们询问一次 \([1, n]\) 和两次长度为 \(\frac{n}{2}\) 的区间。
不妨问 \([1, n], [1, \frac{n}{2}], [1, \frac{n}{2} + 1]\) 试试。注意到把 \([1, \frac{n}{2} + 1]\) 得到的集合除去 \([1, \frac{n}{2}]\) 中的元素，得到的是左端点在 \([1, \frac{n}{2} + 1]\)，右端点为 \(\frac{n}{2} + 1\) 的子串，可以通过这些串中长度为 \(i\) 除去长度为 \(i - 1\) 的串剩下的字符求出原串 \([1, \frac{n}{2} + 1]\) 中的字符。接下来的任务是求 \([\frac{n}{2} + 2, n]\) 中的字符。
考虑 \([1, n]\) 的集合中所有长度为 \(2\) 的串，除了已知的 \(s[1, \frac{n}{2} + 1]\)，剩下的只有 \(s_n\) 出现 \(1\) 次，\(s[\frac{n}{2} + 2, n - 1]\) 都是出现 \(2\) 次。那么出现次数为奇数的字母就是 \(s_n\)。
再考虑 \([1, n]\) 中所有长度为 \(3\) 的串。除了已知的 \(s[1, \frac{n}{2} + 1]\) 和 \(s_n\)，剩下的只有 \(s_{n - 1}\) 出现 \(2\) 次，\(s[\frac{n}{2} + 2, n - 2]\) 都是出现 \(3\) 次。那么出现次数 \(\bmod\ 3 = 2\) 的字母就是 \(s_n\)。
以此类推，所有长度为 \(i\) 的串中，除去已知的，只有 \(s_{n - i + 2}\) 出现 \(i - 1\) 次，其他未知的都出现 \(i\) 次。所以出现次数 \(\bmod\ i = i - 1\) 的字母就是 \(s_{n - i + 2}\)。这样可以确定 \([\frac{n}{2} + 2, n]\) 的部分。
总共使用 \(3\) 次询问，总子串个数 \(\approx 0.75n^2\)。
code
// Problem: C2. Madhouse (Hard version)
// Contest: Codeforces - Codeforces Round 612 (Div. 1)
// URL: https://codeforces.com/problemset/problem/1286/C2
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
int n, a[26];
string b[maxn];
char ans[maxn];
vector<string> vc[maxn];
inline multiset<string> ask(int l, int r) {
int n = r - l + 1;
printf("? %d %d\n", l, r);
fflush(stdout);
multiset<string> S;
for (int _ = 0; _ < n * (n + 1) / 2; ++_) {
string s;
cin >> s;
sort(s.begin(), s.end());
S.insert(s);
}
return S;
}
void solve() {
scanf("%d", &n);
if (n <= 3) {
string ans = "";
for (int i = 1; i <= n; ++i) {
ans += *ask(i, i).begin();
}
printf("! %s\n", ans.c_str());
return;
}
auto A = ask(1, n), B = ask(1, n / 2), C = ask(1, n / 2 + 1);
auto D = C;
for (auto s : B) {
D.erase(D.find(s));
}
int tot = 0;
for (auto s : D) {
b[++tot] = s;
}
sort(b + 1, b + tot + 1, [&](const string &a, const string &b) {
return a.size() > b.size();
});
ans[tot] = b[tot][0];
for (int i = tot - 1; i; --i) {
mems(a, 0);
for (char c : b[i]) {
++a[c - 'a'];
}
for (char c : b[i + 1]) {
--a[c - 'a'];
}
for (int j = 0; j < 26; ++j) {
if (a[j]) {
ans[i] = 'a' + j;
break;
}
}
}
for (auto s : C) {
A.erase(A.find(s));
}
for (auto s : A) {
vc[(int)s.size()].pb(s);
}
for (int i = 2; i <= n - n / 2; ++i) {
mems(a, 0);
for (auto s : vc[i]) {
for (char c : s) {
++a[c - 'a'];
}
}
for (int j = n / 2 + 1, k = i - 1; k; --j, --k) {
a[ans[j] - 'a'] -= k;
}
for (int j = n, k = 1; k <= i - 2; --j, ++k) {
a[ans[j] - 'a'] -= k;
}
for (int j = 0; j < 26; ++j) {
if (a[j] % i == i - 1) {
ans[n - i + 2] = 'a' + j;
break;
}
}
}
printf("! %s\n", ans + 1);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}