Hướng dẫn giải của Thi thử HSG9 2026 - Ngày 4 - Dãy

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Nhận xét quan trọng của bài toán là việc ~r - l~ luôn cố định do đó ta có thể sử dụng thuật toán cửa sổ trượt (sliding window) kết hợp với cập nhật trên cây Fenwick (BIT) và trả lời các truy vấn offline bằng Walk on BIT (chia nhị phân trên cây BIT).

Cụ thể, ta có thể thực hiện như sau:

  • Ta duy trì hai con trỏ ~i~ và ~j~, ban đầu ~i = 1~ và ~j = r - l~.
  • Ban đầu, với mọi ~1\leq o\leq r - l~ ta cập nhật trên cây BIT tăng giá trị ở vị trí ~a_o~ lên ~1~ đơn vị.
  • Với mỗi vị trí ~j~, ta trả lời toàn bộ các truy vấn có ~r = j~ bằng cách tìm kiếm nhị phân trên cây BIT giá trị bé nhất mà số lượng phần tử bé hơn hoặc bằng nó lớn hơn hoặc bằng ~k~, giá trị đó là đáp án cho truy vấn.
  • Cuối cùng, ta cập nhật giảm giá trị ở vị trí ~a_i~ trên cây BIT đi ~1~ đơn vị và ở vị trí ~a_{j + 1}~ lên ~1~ đơn vị. Tăng cả ~i~ và ~j~ lên ~1~.

Thử thách: Bài toán này có cách giải khác mà không cần quan tâm đến giá trị ~r - l~, liệu bạn có thể giải được ?

Code mẫu (bài nộp của người dùng tinozz):

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define pb push_back
#define vec vector
#define um unordered_map
#define us unordered_set
#define ms multiset

#define cocainit ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define koconcainit return 0;
#define debug(x) cout << x << ' ';
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Forn(i, b, a) for(int i = b; i >= a; --i)
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define MASK(i) (1 << (i))
#define BIT(i, x) (((x) >> (i)) & 1)
#define fileinp(x) freopen((x + ".inp").c_str(), "r", stdin)
#define fileout(x) freopen((x + ".out").c_str(), "w", stdout)
#define iiiiii iiiiii
const ll INF = 1e9;
const int mx = 2e5 + 5;
const int mx2 = 5e5 + 5;
const int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};
const int MOD = 1e9 + 7;
const int MOD2 = 14062008;

struct bit {
    int n;
    vec<int> f;
    bit(int n = 0): n(n), f(n + 1, 0) {}
    void add(int i, int v){
        for(; i <= n; i += i & -i) f[i] += v;
    }
    int kth(int k){
        int i = 0;
        int p = 1;
        while ((p << 1) <= n) p <<= 1;
        for(int d = p; d; d >>= 1){
            int j = i + d;
            if(j <= n && f[j] < k){
                i = j;
                k -= f[j];
            }
        }
        return i + 1;
    }
};

struct qr {
    int l, r, k, id;
};

int n, q, len;
vec<int> a, c, v, ans;
vec<qr> qs;

void input() {
    cin >> n >> q;
    a.assign(n + 1, 0);
    v.clear();
    v.reserve(n);
    For(i, 1, n){
        cin >> a[i];
        v.pb(a[i]);
    }
    qs.resize(q);
    For(i, 0, q - 1){
        cin >> qs[i].l >> qs[i].r >> qs[i].k;
        qs[i].id = i;
    }
}

void solve() {
    sort(all(v));
    v.erase(unique(all(v)), v.end());

    c.assign(n + 1, 0);
    For(i, 1, n){
        c[i] = (lower_bound(all(v), a[i]) - v.begin()) + 1;
    }

    len = qs[0].r - qs[0].l + 1;

    sort(all(qs), [](const qr& x, const qr& y){
        return x.l < y.l;
    });

    bit ft(v.size());
    int cur = 1;
    For(i, 1, len) ft.add(c[i], 1);

    ans.assign(q, 0);

    for (auto &qq : qs) {
        while (cur < qq.l) {
            ft.add(c[cur], -1);
            ft.add(c[cur + len], 1);
            cur++;
        }
        int idv = ft.kth(qq.k);
        ans[qq.id] = v[idv - 1];
    }
}

void output() {
    For(i, 0, q - 1){
        cout << ans[i] << endl;
    }
}

signed main() {
    cocainit;
    string s = "ARR";
    fileinp(s);
    fileout(s);

    int test = 1;
    while (test--) {
        input();
        solve();
        output();
    }
    koconcainit;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.