# D. Guess The String
link : https://codeforces.com/problemset/problem/1697/D

tóm tắt đề : cho xâu độ dài cố định n, có 2 loại truy vấn:
1 : hỏi 1 kí tự tại i (tối đa 26 lần hỏi)
2 : hỏi có bao nhiêu kí tự khác nhau trong [l...r] (tối đa 6000 lần hỏi)

Mục tiêu : đoán xâu ban đầu

+ suy nghĩ 1 : thao tác 1 rất có thể là để đoán vừa đủ lượng kí tự, thao tác 2 có vẻ là dùng thoải mái.

+ suy nghĩ 2 : đã có cách để dùng chặt nhị phân để đoán được, tuy nhiên số thao tác loại 2 cần hơn 8000 lần hỏi.

+ suy nghĩ 3 : giảm số lượng vị trí cần quan tâm, đưa về mỗi vị trí hỏi tối đa log2(26) lần hỏi.

code AC :
:::spoiler

#include<bits/stdc++.h>
#define pii pair<int, int>
#define REP(i, a, b) for (int i = (a); i <= (b); ++i)
#define X first
#define Y second

using namespace std;
const int mxn = 5e5 + 5;
char s[mxn];

char fi(int x)
{
    set<char> tmp;
    vector<int> tap;
    for (int i = x - 1; i >= 1; --i)
        if (tmp.find(s[i]) == tmp.end())
        {
            tmp.insert(s[i]);
            tap.push_back(i);
        }

    reverse(tap.begin(), tap.end());
    int l = 0, r = tap.size();
    while(l < r)
    {
        int mid = (l + r)/2;
        cout << "? 2 " << tap[mid] << ' ' << x << endl;
        int y; cin >> y;
        if (y > tap.size() - mid) r = mid;
        else l = mid + 1;
    }
    return s[tap[l - 1]];
}

int main() {
    int n; cin >> n;
    cout << "? 1 1" << endl;
    cin >> s[1];
    int tong = 1;

    REP(i, 2, n)
    {
        cout << "? 2 1 " << i << endl;
        int x; cin >> x;
        if (x > tong)
        {
            cout << "? 1 " << i << endl;
            cin >> s[i];
            ++tong;
        }
        else s[i] = fi(i);
    }

    cout << "! ";
    REP(i, 1, n) cout << s[i];
}