Bình luận

• 
  

  2

  

  vominhmanh10  đã bình luận lúc 4, Tháng 12, 2025, 3:07 ← sửa 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";
          }
      }
  }
  

• 
  

  1

  

  ledinhdat189  đã bình luận lúc 9, Tháng 8, 2025, 10:30

  dùng map thay multiset là AC

• 
  

  4

  

  kuriyama_san  đã bình luận lúc 12, Tháng 10, 2024, 10:26

  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  đã bình luận lúc 8, Tháng 10, 2024, 13:46

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

• 
  

  -15

  

  hieudeptrai  đã bình luận lúc 29, Tháng 7, 2024, 3:42

  AI BỊ TLE THÌ THỬ THÊM PRAGMA VÀO NHA CÓ KHI LẠI AC AHIHI

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  -10

  

  Spectrum3563  đã bình luận lúc 5, Tháng 6, 2024, 12:35

  bài này build segment tree suy nghĩ thông thường thì mất tận 2.9s dùng scanf/printf có cách nào tối ưu hơn k?

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  -3

  

  flechilavt  đã bình luận lúc 2, Tháng 12, 2023, 2:23

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

• 
  

  0

  

  Huy_inIT  đã bình luận lúc 4, Tháng 10, 2024, 7:29

  merge sort tree

• 
  

  -5

  

  loitran1001  đã bình luận lúc 27, Tháng 11, 2023, 4:41

  bài này cài multiset nhưng vẫn hơn 3s vậy mn có cách nào giảm được thời gian không?

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  -7

  

  loitran1001  đã bình luận lúc 27, Tháng 11, 2023, 5:08

  chỉnh sửa: Đã AC, game này nhân phẩm

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  14

  

  tink29lenhuttri32  đã bình luận lúc 14, Tháng 9, 2023, 2:39

  VanvatthuaFuxuan

• 
  

  -5

  

  anita  đã bình luận lúc 26, Tháng 10, 2023, 12:51

  vanvatthuaOtto

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  -9

  

  Huuuuuuh  đã bình luận lúc 7, Tháng 3, 2022, 9:47

  Ai cho mình xin test của bài này với

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  -19

  

  vqt  đã bình luận lúc 24, Tháng 7, 2022, 5:48

  Chung ý kiến ạ :<

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  158

  

  YugiHackerKhongCopCode  đã bình luận lúc 22, Tháng 12, 2021, 9:25

  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))~