fork download
copy 
  1. #pragma GCC optimize("O3,unroll-loops")
  2. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <cmath>
  7.  
  8. using namespace std;
  9.  
  10. const int MOD = 1e9 + 7;
  11. const int MAXN = 100005;
  12. const int MAX_VAL = 100005;
  13.  
  14. // Cấu hình kích thước block tối ưu qua thực nghiệm
  15. const int B_1 = 450; // Kích thước khối theo chỉ số mảng
  16. const int B_2 = 320; // Kích thước khối theo trục giá trị
  17.  
  18. const int K1 = (MAXN / B_1) + 5;
  19. const int K2 = (MAX_VAL / B_2) + 5;
  20.  
  21. int n, q;
  22. int a[MAXN];
  23. long long inv[MAX_VAL];
  24.  
  25. // ===== CẤU TRÚC CHIA CĂN 2 LẦN =====
  26. // Tiết kiệm bộ nhớ bằng cách dùng short cho mảng đếm tích lũy (vì B_1 = 450 < 32767)
  27. short pref_in_vb_cnt[K1][MAX_VAL];
  28. int pref_in_vb_prod[K1][MAX_VAL];
  29.  
  30. int pref_b_cnt[K1][K2];
  31. int pref_b_prod[K1][K2];
  32.  
  33. int block_total_prod[K1];
  34.  
  35. // Hàm tính lũy thừa nhanh
  36. long long power_mod(long long base, long long exp) {
  37.     if (exp < 0) return 0;
  38.     long long res = 1;
  39.     base %= MOD;
  40.     while (exp > 0) {
  41.         if (exp % 2 == 1) res = res * base % MOD;
  42.         base = base * base % MOD;
  43.         exp /= 2;
  44.     }
  45.     return res;
  46. }
  47.  
  48. // Xây dựng cấu trúc dữ liệu ban đầu
  49. void build_structure() {
  50.     int num_blocks = (n + B_1 - 1) / B_1;
  51.     int num_val_blocks = (MAX_VAL + B_2 - 1) / B_2;
  52.  
  53.     for (int b = 0; b < num_blocks; ++b) {
  54.         block_total_prod[b] = 1;
  55.         int start_idx = b * B_1;
  56.         int end_idx = min(n - 1, (b + 1) * B_1 - 1);
  57.  
  58.         // Đếm tần suất thô của các phần tử trong khối b
  59.         vector<int> local_cnt(MAX_VAL, 0);
  60.         for (int i = start_idx; i <= end_idx; ++i) {
  61.             local_cnt[a[i]]++;
  62.             block_total_prod[b] = 1LL * block_total_prod[b] * a[i] % MOD;
  63.         }
  64.  
  65.         // Xây dựng tiền tố tích lũy lồng nhau trên trục giá trị
  66.         int current_cnt = 0;
  67.         long long current_prod = 1;
  68.  
  69.         for (int vb = 0; vb < num_val_blocks; ++vb) {
  70.             int v_start = vb * B_2;
  71.             int v_end = min(MAX_VAL - 1, (vb + 1) * B_2 - 1);
  72.  
  73.             int vb_cnt = 0;
  74.             long long vb_prod = 1;
  75.  
  76.             for (int v = v_start; v <= v_end; ++v) {
  77.                 if (local_cnt[v] > 0) {
  78.                     long long p = power_mod(v, local_cnt[v]);
  79.                     vb_prod = vb_prod * p % MOD;
  80.                     vb_cnt += local_cnt[v];
  81.                 }
  82.                 pref_in_vb_prod[b][v] = vb_prod;
  83.                 pref_in_vb_cnt[b][v] = vb_cnt;
  84.             }
  85.  
  86.             current_cnt += vb_cnt;
  87.             current_prod = current_prod * vb_prod % MOD;
  88.  
  89.             pref_b_cnt[b][vb] = current_cnt;
  90.             pref_b_prod[b][vb] = current_prod;
  91.         }
  92.     }
  93. }
  94.  
  95. // Thao tác cập nhật điểm online O(B_2 + V/B_2)
  96. void update(int p, int new_v) {
  97.     int old_v = a[p];
  98.     if (old_v == new_v) return;
  99.  
  100.     int b = p / B_1;
  101.     long long old_inv = inv[old_v];
  102.     int num_val_blocks = (MAX_VAL + B_2 - 1) / B_2;
  103.  
  104.     // 1. Loại bỏ giá trị cũ khỏi cấu trúc tiền tố giá trị
  105.     int old_vb = old_v / B_2;
  106.     int end_old_vb = min(MAX_VAL - 1, (old_vb + 1) * B_2 - 1);
  107.     for (int v = old_v; v <= end_old_vb; ++v) {
  108.         pref_in_vb_cnt[b][v]--;
  109.         pref_in_vb_prod[b][v] = 1LL * pref_in_vb_prod[b][v] * old_inv % MOD;
  110.     }
  111.     for (int vb = old_vb; vb < num_val_blocks; ++vb) {
  112.         pref_b_cnt[b][vb]--;
  113.         pref_b_prod[b][vb] = 1LL * pref_b_prod[b][vb] * old_inv % MOD;
  114.     }
  115.  
  116.     // 2. Thêm giá trị mới vào cấu trúc tiền tố giá trị
  117.     int new_vb = new_v / B_2;
  118.     int end_new_vb = min(MAX_VAL - 1, (new_vb + 1) * B_2 - 1);
  119.     for (int v = new_v; v <= end_new_vb; ++v) {
  120.         pref_in_vb_cnt[b][v]++;
  121.         pref_in_vb_prod[b][v] = 1LL * pref_in_vb_prod[b][v] * new_v % MOD;
  122.     }
  123.     for (int vb = new_vb; vb < num_val_blocks; ++vb) {
  124.         pref_b_cnt[b][vb]++;
  125.         pref_b_prod[b][vb] = 1LL * pref_b_prod[b][vb] * new_v % MOD;
  126.     }
  127.  
  128.     // 3. Cập nhật tích tổng của khối và lưu vào mảng gốc
  129.     block_total_prod[b] = 1LL * block_total_prod[b] * old_inv % MOD * new_v % MOD;
  130.     a[p] = new_v;
  131. }
  132.  
  133. // Truy vấn tử số S_X = tích các min(a_i, X) trong O(B_1 + N/B_1)
  134. pair<long long, int> query_S(int L, int R, int X) {
  135.     if (X <= 0) return {0, 0};
  136.     if (X >= MAX_VAL) X = MAX_VAL - 1;
  137.  
  138.     long long ans_prod = 1;
  139.     int ans_cnt = 0;
  140.  
  141.     int bl = L / B_1;
  142.     int br = R / B_1;
  143.  
  144.     if (bl == br) { // Nằm chung 1 khối chỉ số
  145.         for (int i = L; i <= R; ++i) {
  146.             if (a[i] <= X) {
  147.                 ans_prod = ans_prod * a[i] % MOD;
  148.                 ans_cnt++;
  149.             }
  150.         }
  151.     } else {
  152.         // Phần lẻ khối đầu
  153.         int end_bl = (bl + 1) * B_1 - 1;
  154.         for (int i = L; i <= end_bl; ++i) {
  155.             if (a[i] <= X) {
  156.                 ans_prod = ans_prod * a[i] % MOD;
  157.                 ans_cnt++;
  158.             }
  159.         }
  160.         // Các khối nguyên ở giữa lấy kết quả O(1)
  161.         int X_vb = X / B_2;
  162.         for (int b = bl + 1; b < br; ++b) {
  163.             if (X_vb > 0) {
  164.                 ans_prod = ans_prod * pref_b_prod[b][X_vb - 1] % MOD;
  165.                 ans_cnt += pref_b_cnt[b][X_vb - 1];
  166.             }
  167.             ans_prod = ans_prod * pref_in_vb_prod[b][X] % MOD;
  168.             ans_cnt += pref_in_vb_cnt[b][X];
  169.         }
  170.         // Phần lẻ khối cuối
  171.         int start_br = br * B_1;
  172.         for (int i = start_br; i <= R; ++i) {
  173.             if (a[i] <= X) {
  174.                 ans_prod = ans_prod * a[i] % MOD;
  175.                 ans_cnt++;
  176.             }
  177.         }
  178.     }
  179.     return {ans_prod, ans_cnt};
  180. }
  181.  
  182. // Truy vấn mẫu số D = tích các a_i trong O(B_1 + N/B_1)
  183. long long query_D(int L, int R) {
  184.     long long ans = 1;
  185.     int bl = L / B_1;
  186.     int br = R / B_1;
  187.  
  188.     if (bl == br) {
  189.         for (int i = L; i <= R; ++i) ans = ans * a[i] % MOD;
  190.     } else {
  191.         int end_bl = (bl + 1) * B_1 - 1;
  192.         for (int i = L; i <= end_bl; ++i) ans = ans * a[i] % MOD;
  193.         for (int b = bl + 1; b < br; ++b) ans = ans * block_total_prod[b] % MOD;
  194.         int start_br = br * B_1;
  195.         for (int i = start_br; i <= R; ++i) ans = ans * a[i] % MOD;
  196.     }
  197.     return ans;
  198. }
  199.  
  200. int main() {
  201.     // Tối ưu hóa luồng I/O
  202.     ios_base::sync_with_stdio(false);
  203.     cin.tie(NULL);
  204.  
  205.     // Tính trước nghịch đảo modulo tuyến tính O(MAX_VAL)
  206.     inv[1] = 1;
  207.     for (int i = 2; i < MAX_VAL; ++i) {
  208.         inv[i] = MOD - MOD / i * inv[MOD % i] % MOD;
  209.     }
  210.  
  211.     if (!(cin >> n)) return 0;
  212.     for (int i = 0; i < n; ++i) cin >> a[i];
  213.  
  214.     build_structure();
  215.  
  216.     cin >> q;
  217.     while (q--) {
  218.         int type;
  219.         cin >> type;
  220.         if (type == 1) {
  221.             int p, v;
  222.             cin >> p >> v;
  223.             --p; // Chuyển về 0-indexed
  224.             update(p, v);
  225.         } else {
  226.             int L, R, X;
  227.             cin >> L >> R >> X;
  228.             --L; --R; // Chuyển về 0-indexed
  229.  
  230.             int window_size = R - L + 1;
  231.  
  232.             // Tính P(max <= X)
  233.             auto S_X = query_S(L, R, X);
  234.             long long total_S_X = S_X.first * power_mod(X, window_size - S_X.second) % MOD;
  235.  
  236.             // Tính P(max <= X-1)
  237.             long long total_S_X_minus_1 = 0;
  238.             if (X - 1 > 0) {
  239.                 auto S_X_1 = query_S(L, R, X - 1);
  240.                 total_S_X_minus_1 = S_X_1.first * power_mod(X - 1, window_size - S_X_1.second) % MOD;
  241.             }
  242.  
  243.             // Kết quả xác suất tích lũy
  244.             long long num = (total_S_X - total_S_X_minus_1 + MOD) % MOD;
  245.             long long den = query_D(L, R);
  246.  
  247.             long long ans = num * power_mod(den, MOD - 2) % MOD;
  248.             cout << ans << "\n";
  249.         }
  250.     }
  251.  
  252.     return 0;
  253. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WvLrQ4
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!