fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int MAXN = 1000005;
  9. const int MAXB = 10005;
  10.  
  11. int n, m, k;
  12. int a[MAXN];
  13. long long b[MAXN];
  14.  
  15. int S;
  16. int num_blocks;
  17.  
  18. int L[MAXB], R[MAXB];
  19. long long lazy[MAXB];
  20.  
  21. // Các mảng 1D liên tục cho hiệu suất Cache (CPU Cache) cực cao
  22. int sorted_a[MAXN];
  23. int orig_idx[MAXN];
  24. long long sum_b[MAXN];
  25.  
  26. struct Update {
  27.     int p;
  28.     long long w;
  29. };
  30. vector<Update> pending[MAXB];
  31.  
  32. // Áp dụng các cập nhật partial bị trì hoãn (Lazy Rebuild)
  33. void commit(int id) {
  34.     if (pending[id].empty()) return;
  35.     int l = L[id], r = R[id];
  36.  
  37.     for (const auto& upd : pending[id]) {
  38.         int limit = upd.p;
  39.         long long w = upd.w;
  40.         for (int i = l; i <= limit; ++i) {
  41.             b[i] += w;
  42.         }
  43.     }
  44.     pending[id].clear();
  45.  
  46.     // Xây dựng lại mảng tổng tiền tố
  47.     long long cur = 0;
  48.     for (int i = l; i <= r; ++i) {
  49.         cur += b[orig_idx[i]];
  50.         sum_b[i] = cur;
  51.     }
  52. }
  53.  
  54. void update_partial(int id, int p, long long w) {
  55.     pending[id].push_back({p, w});
  56. }
  57.  
  58. long long query_full(int id, int d) {
  59.     commit(id); // Đồng bộ dữ liệu trước khi truy vấn
  60.     int l = L[id], r = R[id];
  61.  
  62.     // Dùng upper_bound với greater<int> để tìm phần tử đầu tiên nhỏ hơn d
  63.     int count = upper_bound(sorted_a + l, sorted_a + r + 1, d, greater<int>()) - (sorted_a + l);
  64.     if (count == 0) return 0;
  65.  
  66.     return sum_b[l + count - 1] + (long long)count * lazy[id];
  67. }
  68.  
  69. long long query_partial(int id, int p, int d) {
  70.     commit(id); // Đồng bộ dữ liệu
  71.     long long ans = 0;
  72.     int l = L[id];
  73.     for (int i = l; i <= p; ++i) {
  74.         if (a[i] >= d) {
  75.             ans += b[i] + lazy[id];
  76.         }
  77.     }
  78.     return ans;
  79. }
  80.  
  81. int main() {
  82.     // Tối ưu hóa I/O tốc độ cao
  83.     ios_base::sync_with_stdio(false);
  84.     cin.tie(NULL);
  85.  
  86.     if (!(cin >> n >> m >> k)) return 0;
  87.  
  88.     for (int i = 0; i < n; ++i) {
  89.         cin >> a[i];
  90.         b[i] = 0;
  91.     }
  92.  
  93.     // Thiết lập kích thước block tối ưu
  94.     S = max(100, (int)sqrt(n * 10));
  95.     num_blocks = (n + S - 1) / S;
  96.  
  97.     for (int i = 0; i < num_blocks; ++i) {
  98.         L[i] = i * S;
  99.         R[i] = min(n - 1, (i + 1) * S - 1);
  100.         lazy[i] = 0;
  101.  
  102.         vector<pair<int, int>> temp;
  103.         temp.reserve(R[i] - L[i] + 1);
  104.         for (int j = L[i]; j <= R[i]; ++j) {
  105.             temp.push_back({a[j], j});
  106.         }
  107.  
  108.         // Sắp xếp các phần tử trong block giảm dần theo a_i
  109.         sort(temp.begin(), temp.end(), [](const pair<int,int>& x, const pair<int,int>& y){
  110.             return x.first > y.first;
  111.         });
  112.  
  113.         for (int j = 0; j < (int)temp.size(); ++j) {
  114.             sorted_a[L[i] + j] = temp[j].first;
  115.             orig_idx[L[i] + j] = temp[j].second;
  116.             sum_b[L[i] + j] = 0;
  117.         }
  118.     }
  119.  
  120.     int q = m + k;
  121.     while (q--) {
  122.         int type;
  123.         cin >> type;
  124.         if (type == 1) {
  125.             int p;
  126.             long long w;
  127.             cin >> p >> w;
  128.             p--; // Chuyển sang 0-based index
  129.             for (int i = 0; i < num_blocks; ++i) {
  130.                 if (R[i] <= p) {
  131.                     lazy[i] += w;
  132.                 } else if (L[i] <= p) {
  133.                     update_partial(i, p, w);
  134.                     break;
  135.                 }
  136.             }
  137.         } else if (type == 2) {
  138.             int p, d;
  139.             cin >> p >> d;
  140.             p--; // Chuyển sang 0-based index
  141.             long long ans = 0;
  142.             for (int i = 0; i < num_blocks; ++i) {
  143.                 if (R[i] <= p) {
  144.                     ans += query_full(i, d);
  145.                 } else if (L[i] <= p) {
  146.                     ans += query_partial(i, p, d);
  147.                     break;
  148.                 }
  149.             }
  150.             cout << ans << "\n";
  151.         }
  152.     }
  153.  
  154.     return 0;
  155. }
  156.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vk4mAM
language:
C++14 (gcc 8.3)
created:
2 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!