Subtask 1: Số truy vấn tối đa: ~n^2~

Với việc có ~n~ nút lá và ~C_{n}^{2}~ cách chọn cặp ~(l, r)~ để hỏi giá trị ~f(l, r)~, bài toán trở thành việc xây dựng lại cây nhị phân từ bảng giá trị này.

Nhận xét là ta có thể dựa vào các cặp ~(l, r)~ có ~f(l, r) = 1~:

• Trường hợp ~r - l + 1 = 2~: Tức là hai nút lá ~l~ và ~r~ có cùng một cha trực tiếp. Ta gán nút cha cho chúng và coi nút cha này đại diện cho khoảng ~[l, r]~.

• Trường hợp ~r - l + 1 > 2~: Tức là khoảng này chứa nhiều hơn 2 nút lá. Ta tìm vị trí ~k~ (~l \le k < r~) sao cho ~f(l, k) = 1~ và ~f(k + 1, r) = 1~ để xác định hai nút con của nút hiện tại.

Subtask 2: Số truy vấn tối đa: ~2 \times n~

Ta tối ưu bằng cách sử dụng cấu trúc Stack. Ý tưởng là duy trì các cây con đã dựng được trong stack và gộp chúng lại ngay khi có thể. Mỗi phần tử trong Stack lưu một nút đại diện cho khoảng lá ~[L, R]~.

Với mỗi nút lá ~i~ từ ~1~ đến ~n~:

• Đẩy nút lá ~i~ vào stack, đại diện cho khoảng ~(i, i)~.

• Trong khi Stack có ít nhất 2 nút:

  • Gọi ~B~ là nút trên đỉnh stack (khoảng ~[B_L, B_R]~) và ~A~ là nút ngay dưới ~B~ (khoảng ~[A_L, A_R]~).

  • Thực hiện truy vấn ~f(A_L, B_R)~.

  • Nếu ~f(A_L, B_R) = 1~: Ta lấy ~A~ và ~B~ ra khỏi stack, tạo nút cha mới đại diện cho khoảng gộp ~[A_L, B_R]~, sau đó đẩy nút cha này lại vào stack.

  • Nếu ~f(A_L, B_R) \neq 1~: Dừng việc gộp và chuyển sang nút lá tiếp theo.

Sau khi duyệt hết ~n~ lá, stack sẽ chỉ còn lại đúng một nút đại diện cho toàn bộ cây.

Về số lượng truy vấn, ta có:

• Khi gặp truy vấn có kết quả ~f = 1~ sẽ là một lần gộp thành công, và số lượng nút trong stack giảm đi 1. Để từ ~n~ lá còn lại 1 gốc, ta cần đúng ~n - 1~ lần gộp thành công.

• Khi ta gặp điều kiên ~f \neq 1~, lúc này sẽ là điều kiện dừng cho mỗi lá khi được đưa vào hoặc sau khi gộp. Có tối đa ~n~ lần kiểm tra.

Vậy tổng số truy vấn tối đa là ~(n - 1) + n = 2n - 1~, thỏa mãn yêu cầu đề bài.

P.S: Bài này có lời giải tối ưu hơn khi chỉ sử dụng đúng ~n~ truy vấn, cách làm xin dành lại cho độc giả tự khám phá.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n; scanf("%d", &n);

    vector<int> l(2*n, -1), r(2*n, -1);

    stack<int> st;
    st.push(1);

    int last_f = 1;
    int id = n+1;
    for(int i = 2; i <= n; ++i) {
        printf("? %d %d\n", 1, i);
        fflush(stdout);
        int f; scanf("%d", &f);

        st.push(i);
        for(int k = 1; k <= last_f + 1 - f; ++k) {
            r[id] = st.top(); st.pop();
            l[id] = st.top(); st.pop();
            st.push(id++);
        }
        last_f = f;
    }

    printf("!");
    for(int i = n+1; i < 2*n; ++i) {
        printf(" %d %d", l[i], r[i]);
    }
    puts("");
    fflush(stdout);
}

int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
}