Educational Segment Tree Contest - ITDS1

View as PDF
Submit solution
Points: 0.04
Time limit: 3.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
Educational Segment Tree Contest - Anh Nguyên
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement

Comments

Please read the guidelines before commenting.


  • 0
    nguyenthenam11042011  commented on April 27, 2026, 2:39 a.m.

    ai dùng ms thì thay đổi kích thước mảng là ok nhé


  • -5
    minh10tincbn  commented on March 25, 2026, 1:32 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 3
    vominhmanh10  commented on Dec. 4, 2025, 3:07 a.m. ← edit 3

    Map nhanh hơn do lưu trùng lặp sẽ chuyển thành đếm tần suất, bài toán quan tâm đến giá trị nên sẽ rất nhanh 

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define se second
#define pii pair< ll, ll>
#define IO ios::sync_with_stdio(0); cin.tie(nullptr)

const ll maxn = 1e5 + 5, inf = 1e18;
map< ll, int> seg[maxn << 2];
ll a[maxn];
inline void build(int idx, int l, int r) {
    if (l == r) {
        seg[idx][a[l - 1]]++;
        return;
    }
    int mid = (l + r) / 2;
    build(idx << 1, l, mid);
    build((idx << 1) | 1, mid + 1, r);
    // gộp map là một phần quan trọng, còn gộp giá trị phải làm thủ công rồi
    seg[idx].insert(seg[idx << 1].begin(), seg[idx << 1].end());
    for (auto &it : seg[idx << 1 | 1]) {
        seg[idx][it.fi] += it.se;
    }
}
inline void update(int idx, int l, int r, int pos, ll x, ll y) {
    if (pos < l || pos > r) return;
    if (l == r) {
        seg[idx][x]--;
        if (seg[idx][x] <= 0) seg[idx].erase(x);
        seg[idx][y]++;
        a[pos - 1] = y;
        return;
    }
    if (pos >= l && pos <= r) {
        seg[idx][x]--;
        if (seg[idx][x] <= 0) seg[idx].erase(x);
        seg[idx][y]++;
    }
    int mid = (l + r) / 2;
    update(idx << 1, l, mid, pos, x, y);
    update(idx << 1 | 1, mid + 1, r, pos, x, y);
}
inline ll query(int idx, int l, int r, int L, int R, ll x) {
    if (r < L || l > R) return -1;
    if (l >= L && r <= R) {
        auto it = seg[idx].lower_bound(x);
        return ((it == seg[idx].end()) ? -1 : it->fi);
    }
    int mid = (l + r) / 2;
    ll left = query(idx << 1, l, mid, L, R, x);
    ll right = query(idx << 1 | 1, mid + 1, r, L, R, x);
    if (left == -1) return right;
    if (right == -1) return left;
    return min(left, right);
}
int main() {
    IO;
    int n, q; cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int pos; ll x; cin >> pos >> x;
            update(1, 1, n, pos, a[pos - 1], x);
        } else {
            int l, r; ll x; cin >> l >> r >> x;
            ll ans = query(1, 1, n, l, r, x);
            cout << ans << "\n";
        }
    }
}

  • 0
    ledinhdat189  commented on Aug. 9, 2025, 10:30 a.m.

    dùng map thay multiset là AC


  • 5
    kuriyama_san  commented on Oct. 12, 2024, 10:26 a.m.

    Các bạn có thể xem hướng dẫn chi tiết trên Wiki của VNOI, rất dễ hiểu và dễ cài đặt: https://wiki.vnoi.info/algo/data-structures/segment-tree-basic.md ví dụ 3


  • 2
    khai05  commented on Oct. 8, 2024, 1:46 p.m.

    Thay multiset thành map nó chạy max 2,5s :))


  • -15
    hieudeptrai  commented on July 29, 2024, 3:42 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -10
    Spectrum3563  commented on June 5, 2024, 12:35 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -3
    flechilavt  commented on Dec. 2, 2023, 2:23 a.m.

    này làm sao viết hàm build v mn


    • 0
      Huy_inIT  commented on Oct. 4, 2024, 7:29 a.m.

      merge sort tree


  • -5
    loitran1001  commented on Nov. 27, 2023, 4:41 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -7
      loitran1001  commented on Nov. 27, 2023, 5:08 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 14
    tink29lenhuttri32  commented on Sept. 14, 2023, 2:39 a.m.

    VanvatthuaFuxuan


    • -5
      anita  commented on Oct. 26, 2023, 12:51 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -9
    Huuuuuuh  commented on March 7, 2022, 9:47 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -19
      vqt  commented on July 24, 2022, 5:48 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 161
    YugiHackerKhongCopCode  commented on Dec. 22, 2021, 9:25 a.m.

    Cmt này spoil thuật!

    Thuật 1: IT

    Mỗi node là 1 set/multiset

    Truy vấn update

    Khi đoạn cần update có ~l==r~ thì ta xóa số ~a[i]~ cũ và thêm ~v~ vào multiset

    Trường hợp ~l~ != ~r~ thì ta kiểm tra cây con trái hay cây con phải vừa bị xóa số, ta xóa số đó đi và thêm v vào multiset

    Ngoài ra còn có cách đơn giản hơn là khi ~l==r~ thì tất cả các đoạn chứa ~a[i]~ sẽ đều phải xóa 1 giá trị ~a[i]~ và thêm 1 giá trị ~v~, ta sẽ dùng 1 vòng while chạy ngược về để update.

    Truy vấn get

    Tìm số nhỏ nhất ~\geq k~ trong đoạn từ ~l~ đến ~r~ và return

    Độ phức tạp:

    Bộ nhớ: ~N.log(N)~ (vì độ sâu tối đa là log(N)).

    Thời gian: ~N.log(N)^2~ (thời gian tìm kiếm trên set là ~logN~).

    Thuật 2: Chia căn

    Đặt block = ~sqrt(N)~

    Mỗi đoạn độ dài block ta sẽ cho vào 1 multiset

    Truy vấn update

    Xóa ~a[i]~ cũ trong block chứa ~i~, thêm ~a[i]~ mới vào.

    Truy vấn get

    Tìm trong đoạn từ ~l~ đến ~r~ có bao nhiêu block hoàn chỉnh và get trong các block đó, còn phần dư 2 bên thì duyệt trâu.

    Độ phức tạp:

    Bộ nhớ: ~N~

    Thời gian: ~N + M.sqrt(N).log(sqrt(N))~