fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  6.  
  7. struct BIT {
  8.     int _n;
  9.     vector<long long> _tree;
  10.  
  11.     void init(int get_n) {
  12.         _n = get_n, _tree.assign(get_n, 0);
  13.     }
  14.  
  15.     void add(int _at, int _value) {
  16.         for (int i = _at + 1; i <= _n; i += i & -i)
  17.             _tree[i - 1] += _value;
  18.     }
  19.  
  20.     long long sum(int _exc) {
  21.         long long _ans = 0;
  22.         for (int i = _exc; i > 0; i -= i & -i)
  23.             _ans += _tree[i - 1];
  24.         return _ans;
  25.     }
  26. };
  27.  
  28. void get_shit_done() {
  29.     int big = 2'000'01;
  30.  
  31.     int n, q;
  32.     cin >> n >> q;
  33.  
  34.     vector<int> a(n);
  35.     for (int i = 0; i < n; ++i) cin >> a[i];
  36.  
  37.     vector<vector<pair<int, int>>> L(n), R(n);
  38.     for (int iq = 0, l, r, x; iq < q; ++iq) {
  39.         cin >> l >> r >> x;
  40.         --l, --r;
  41.         L[l].push_back({ iq, x });
  42.         R[r].push_back({ iq, x });
  43.     }
  44.  
  45.     BIT tree;
  46.     vector<long long> pref(q), del(q);
  47.  
  48.     long long sum = 0;
  49.     tree.init(big);
  50.     for (int i = 0; i < n; ++i) {
  51.         for (auto [id, x] : L[i]) {
  52.             del[id] = del[id] - tree.sum(x + 1);
  53.             pref[id] = pref[id] - sum;
  54.         }
  55.         sum = sum + a[i];
  56.  
  57.         int at = 1;
  58.         while (at <= a[i]) {
  59.             int t = a[i] / at;
  60.             int nxt = a[i] / t + 1;
  61.             tree.add(at, t);
  62.             tree.add(nxt, -t);
  63.             at = nxt;
  64.         }
  65.  
  66.         for (auto [id, x] : R[i]) {
  67.             del[id] = del[id] + tree.sum(x + 1);
  68.             pref[id] = pref[id] + sum;
  69.             del[id] = del[id] * x;
  70.         }
  71.     }
  72.  
  73.     for (int i = 0; i < q; ++i)
  74.         cout << pref[i] - del[i] << ' ';
  75. }
  76.  
  77. signed main() {
  78.     _3bkarm
  79.  
  80.     int ts = 1;
  81. //    cin >> ts;
  82.     while (ts--) {
  83.         get_shit_done();
  84.     }
  85.  
  86.     return 0;
  87. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/edX9b8
language:
C++ (gcc 8.3)
created:
6 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!