Bình luận

• 
  

  -1

  

  deanqkhanh  đã bình luận lúc 19, Tháng 1, 2026, 13:42

  Lời giải: Chia căn trên Tập hợp (Square Root Decomposition)

  1. Phân tích bài toán

  Bài toán yêu cầu thực hiện các thao tác cập nhật giá trị và truy vấn tổng trên các tập hợp phần tử của một mảng. Khó khăn nằm ở chỗ một phần tử có thể nằm trong rất nhiều tập hợp khác nhau.

  Dữ kiện quan trọng: Tổng kích thước của tất cả các tập hợp không vượt quá 100,000. Đây là dấu hiệu để sử dụng kỹ thuật chia căn.

  ---

  2. Ý tưởng chính

  Chúng ta chia các tập hợp thành hai loại dựa trên số lượng phần tử của chúng (gọi ngưỡng chia căn là B, thường chọn B khoảng 320):

  • Tập nhẹ (Light sets): Là các tập có số phần tử nhỏ hơn B.
  • Tập nặng (Heavy sets): Là các tập có số phần tử từ B trở lên.

  Vì tổng số phần tử của tất cả các tập là 100,000, nên số lượng tập nặng sẽ không bao giờ vượt quá 312 tập (100,000 chia cho 320). Số lượng tập nặng ít chính là chìa khóa để tối ưu.

  ---

  3. Các thành phần lưu trữ và Tiền xử lý

  Để giải bài này, ta cần các mảng sau:

  1. Mảng A: Lưu giá trị gốc của các phần tử.
  2. Mảng sum_heavy: Lưu tổng giá trị hiện tại của các tập nặng.
  3. Mảng lazy_heavy: Lưu giá trị "chờ cộng" cho các tập nặng (khi ta cộng vào một tập nặng, ta không cộng từng phần tử mà chỉ ghi chú vào đây).
  4. Mảng giao điểm cnt[h][k]: Lưu số lượng phần tử chung giữa tập nặng thứ h và tập hợp bất kỳ thứ k.
  5. Mảng belong[i]: Lưu danh sách các tập nặng mà phần tử thứ i thuộc về.

  Bước tiền xử lý:

  • Xác định tập nào là nặng, tập nào là nhẹ.
  • Tính tổng giá trị ban đầu cho các tập nặng.
  • Tính toán trước số lượng phần tử chung giữa các tập nặng với tất cả các tập hợp khác để dùng cho việc tính toán nhanh sau này.

  ---

  4. Cách xử lý các truy vấn

  Thao tác cập nhật (+ k x)

  Đây là thao tác cộng giá trị x vào tất cả phần tử của tập hợp k.

  • Nếu k là tập nặng:

  • Ta chỉ cần cộng x vào biến lazy_heavy của tập đó. Việc này cực nhanh.

  • Nếu k là tập nhẹ:

  • Ta duyệt qua từng phần tử trong tập k và cộng x trực tiếp vào mảng A.
  • Đồng thời, ta phải cập nhật lại giá trị sum_heavy của tất cả các tập nặng có chứa các phần tử vừa được cộng này.

  Thao tác truy vấn tổng (? k)

  Đây là thao tác tính tổng các phần tử hiện có của tập hợp k.

  • Nếu k là tập nặng:
  • Kết quả = (Tổng thực tế sum_heavy) + (Ảnh hưởng từ các lệnh cộng vào các tập nặng khác).

  • Phần ảnh hưởng được tính bằng cách lấy: (Giá trị lazy của tập nặng khác) nhân với (Số phần tử chung giữa tập đó và tập k).

  • Nếu k là tập nhẹ:

  • Ta duyệt qua từng phần tử trong tập k.
  • Giá trị của mỗi phần tử = (Giá trị trong mảng A) + (Tổng các giá trị lazy của các tập nặng chứa phần tử đó).

  ---

  5. Tại sao cách này hiệu quả?

  • Với tập nặng, số lượng tập không quá 320 nên các vòng lặp duyệt qua danh sách tập nặng chạy rất nhanh.
  • Với tập nhẹ, số lượng phần tử không quá 320 nên việc duyệt từng phần tử cũng rất nhanh.
  • Tổng số phép tính cho mỗi truy vấn chỉ rơi vào khoảng vài trăm đến vài nghìn phép tính, hoàn toàn nằm trong giới hạn 1 giây của máy tính (thường xử lý được 100 triệu phép tính mỗi giây).

  ---

  6. Mã nguồn tham khảo (C++)

  #pragma GCC optimize("Ofast")
  #pragma GCC optimize("unroll-loops")
  #pragma GCC optimize("inline")
  #include <iostream>
  #include <vector>
  #include <bitset>
  using namespace std;
  using ll = long long;
  constexpr int B = 320;
  constexpr int LIMIT = (int)1e5;
  
  int main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      int n, m, q;
      cin >> n >> m >> q;
      vector<ll> a(n);
      for (ll &e : a) cin >> e;
      vector<vector<int>> s(m);
      vector<int> heavy;
      vector<int> idh(LIMIT + 1, -1);
      int idx = 0;
      // cerr << "ok";
      for (int i = 0; i < m; ++i){
          int k; cin >> k;
          s[i].resize(k);
          for (int &e : s[i]){
              cin >> e;
              --e;
              // cerr << e << '\n';
          }
          if (s[i].size() > B){
              idh[i] = idx++;
              heavy.push_back(i);
          }
      }
      int H = heavy.size();
      // cout << H;
      vector<ll> sum(H, 0);
      vector<ll> lazy(H, 0);
      for (int i = 0; i < H; ++i){
          for (int j : s[heavy[i]]){
              sum[i] += a[j];
          }
      }
      vector<vector<int>> cnt(H, vector<int>(H, 0));
      bitset<LIMIT + 1> mask;
      for (int h1 = 0; h1 < H; ++h1){
          mask.reset();
          for (int x : s[heavy[h1]]){
              mask[x] = 1;
          }
          for (int h2 = 0; h2 < H; ++h2){
              if (h1 == h2){
                  cnt[h1][h2] = s[heavy[h2]].size();
                  continue;
              }
              if (cnt[h2][h1] != 0){
                  cnt[h1][h2] = cnt[h2][h1];
                  continue;
              }
              int c = 0;
              for (int x : s[heavy[h2]]) if (mask[x]) c++;
              cnt[h1][h2] = c;
          }
      }
      vector<vector<int>> bh(n);
      for (int i = 0; i < H; ++i){
          for (int x : s[heavy[i]]){
              bh[x].push_back(i);
          }
      }
      while (q--){
          char type; cin >> type;
          if (type == '?'){
              int k; cin >> k;
              k--;
              ll ans = 0;
              if (idh[k] != -1){
                  int id = idh[k];
                  ans = sum[id];
                  for (int h = 0; h < H; ++h){
                      ans += lazy[h] * cnt[h][id];
                  }
                  cout << ans << '\n';
              } else {
                  for (int x : s[k]){
                      ll cur = a[x];
                      for (int h : bh[x]){
                          cur += lazy[h];
                      }
                      ans += cur;
                  }
                  cout << ans << '\n';
              }
          } else {
              int k; cin >> k;
              k--;
              int x; cin >> x;
              if (idh[k] != -1){
                  lazy[idh[k]] += x;
              } else {
                  for (int i : s[k]){
                      a[i] += x;
                      for (int h : bh[i]){
                          sum[h] += x;
                      }
                  }
              }
          }
      }
      return 0;
  }
  

• 
  

  5

  

  HoangMC2009  đã bình luận lúc 26, Tháng 11, 2024, 16:13

  https://codeforces.com/problemset/problem/348/C

• 
  

  -22

  

  Loc2008  đã bình luận lúc 27, Tháng 12, 2023, 8:24

  xin downvote

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