Bình luận

• 
  

  4

  

  ProTeam15  đã bình luận lúc 17, Tháng 5, 2026, 4:50

  Bản chất thì ~f(l, r)~ là số nút ít nhất cần để phủ hết đoạn từ ~l \rightarrow r~.

  Để dễ tưởng tượng bài này hơn bạn có thể nghĩ đang làm việc với Segment Tree. Ý tưởng sơ khai là mỗi lẫn bạn truy vấn trên ST thì số lượng nút bạn đụng đến không quá ~log(n)~. Tại sao điều đó lại diễn ra??? Lí do là có sự gộp nút ở đây, nếu như đoạn truy vấn có cả nút ~2\times id ~ và ~2\times id + 1~ thì có thể gộp nó lại thành nút ~id~.

  Qua cái nhìn trên mình có thể đưa ra ý tưởng là nếu hiện tại đang biết đoạn từ ~1 \rightarrow i-1~ sau đó mình thêm nút ~i~ vào thì sẽ xảy ra bao nhiêu lần gộp. Và mỗi lần gộp như thế nó sẽ tác động đến ~2~ đỉnh nào?? Và sau khi gộp ~2~ đỉnh đó lại thì nó biến thành đỉnh nào?? Giả sử gộp ~2~ đỉnh ~A, B~ thành một đỉnh mới là ~C~ thì ta có ~L[C] = A~, ~R[C] = B~.

  Để biết nó tác động đến ~2~ đỉnh nào thì ta cần duy trì các đỉnh hiện tại cần để phủ và đặt ra các câu hỏi ~f(1, i)~ để biết rằng có bao nhiêu lần gộp, từ số lần gộp sẽ thấy cái tập đỉnh duy trì để phủ hết sẽ biến đổi như thế nào.

  Giả sử gọi tập đỉnh duy trì để phủ hết là ST:

  • Ta đang phủ hết đoạn ~1 \rightarrow i - 1~, bây giờ thêm đỉnh ~i~ vào. Suy ra ST sẽ thêm ~i~.
  • Sau đó nó sẽ bắt đầu quá trình gộp, thì gộp sẽ tác động lên ~2~ đỉnh cuối trong ST.
  • Số lần gộp là: ~f(1, i - 1) + 1 - f(1, i)~.
  • Sau khi gộp ~2~ đỉnh cuối lại thì nó tạo ra đỉnh nào?? => Đỉnh tiếp theo chưa xuất hiện.

  Vậy chỉ cần tốn tổng cộng ~n - 1~ truy vấn là có thể xây dựng lại cây ban đầu.

  Code tham khảo:

  #include<bits/stdc++.h>
  #define int long long
  #define oo 1000000000000000000
  #define ii pair<int, int>
  #define fi first
  #define se second
  #define all(x) x.begin(), x.end()
  #define uniq(x) x.erase(unique(all(x)), x.end())
  #define pb push_back
  using namespace std;
  
  const int mod = 998244353;
  
  void add(int &x, int y) {
     x += y;
     if(x >= mod) x -= mod;
  }
  void sub(int &x, int y) {
     x -= y;
     if(x < 0) x += mod;
  }
  
  int n;
  int need[1005]; // f[1 -> i]
  int a[1005], b[1005];
  
  int ask(int l, int r) {
     cout << "? " << l << " " << r << endl;
  
     int cnt; cin >> cnt;
     return cnt;
  } 
  
  void solve() {
  
     /*
     Về mặt bản chất f(l, r) là số đỉnh ít nhất để phủ đoạn đỉnh [L -> R]
  
     nếu mình tính đc số lần các nút gộp vào nhau để tạo thành nút lớn hơn => mình sẽ biết đc đó là 2 nút con của thằng cha.
  
     1 -> (i - 1) thêm i thì gộp bao nhiêu lần?
     hỏi f(1, i) trừ đi f(1, i - 1) + 1 -- +1 là do thêm đỉnh mới là i vào
  
     giờ có số lần gộp rồi thì làm gì??
     mấy lần gộp đó tác động lên thằng nào???
     2 thằng cuối, nma 2 thằng cuối gộp lại thì thành gì???? => thành thằng tiếp theo chưa có
     */
  
     cin >> n;
  
     need[1] = 1;
     for(int i = 2; i <= n; i++) {
         need[i] = ask(1, i);
     }
  
     stack<int> st;
     st.push(1);
     int cur = n;
     for(int i = 2; i <= n; i++) {
         st.push(i);
         int gop = need[i - 1] + 1 - need[i];
         for(int j = 1; j <= gop; j++) {
             int y = st.top(); st.pop();
             int x = st.top(); st.pop();
             cur++;
             a[cur] = x;
             b[cur] = y;
             st.push(cur);
         }
     }
  
     cout << "! ";
     for(int i = n + 1; i < 2 * n; i++) {
         cout << a[i] << " " << b[i] << " ";
     }
     cout << endl;
  }
  
  signed main() {
     ios_base::sync_with_stdio(0);
     cin.tie(0); cout.tie(0);
  
     // if(fopen("a.inp", "r")) {
     //     freopen("a.inp", "r", stdin);
     //     freopen("a.out", "w", stdout);
     // }
  
     int t = 1;
     cin >> t;
     while(t--) {
         solve();
     }
  }