fork download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. #define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
  5. // #define T int t;cin>>t;while(t--)
  6. #define F first
  7. #define S second
  8. #define endl '\n'
  9. #define int long long
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12.  
  13.  
  14. template <typename T>
  15. using ordered_set = tree<
  16.     T,
  17.     null_type,
  18.     less<T>,
  19.     rb_tree_tag,
  20.     tree_order_statistics_node_update
  21. >;
  22.  
  23. template <typename T>
  24. using ordered_set_desc = tree<
  25.     T,
  26.     null_type,
  27.     greater<T>,
  28.     rb_tree_tag,
  29.     tree_order_statistics_node_update
  30. >;
  31.  
  32. const int N = 1e6+6;
  33. vector<int> d(N,1);
  34. void siave() {
  35.     for (int i=2;i<N;i++) {
  36.         for (int j=i;j<N;j+=i) {
  37.             d[j]++;
  38.         }
  39.     }
  40. }
  41.  
  42.  
  43. struct BIT {
  44.     int n;
  45.     vector<int> arr;
  46.     BIT(int _n) {
  47.         n = _n;
  48.         arr.assign(n+1, 0);
  49.     }
  50.  
  51.     void add(int idx,int v) {
  52.         while (idx <= n) {
  53.             arr[idx] += v;
  54.             idx += (idx & -idx);
  55.         }
  56.     }
  57.  
  58.     int get(int idx) {
  59.         int ans = 0;
  60.         while (idx > 0) {
  61.             ans += arr[idx];
  62.             idx -= (idx & -idx);
  63.         }
  64.         return ans;
  65.     }
  66.  
  67.     int get(int l, int r) {
  68.         return get(r) - get(l-1);
  69.     }
  70.  
  71.     void set(int idx, int v) {
  72.         int old = get(idx,idx);
  73.         add(idx, -old + v);
  74.     }
  75. };
  76.  
  77.  
  78. void Abady() {
  79.     siave();
  80.     int n, q; cin >> n >> q;
  81.     BIT bit(n);
  82.     ordered_set<int> st;
  83.     for (int i=1;i<=n;i++) {
  84.         int x; cin >> x;
  85.         bit.add(i,x);
  86.         if (x > 1) st.insert(i);
  87.     }
  88.     while (q--) {
  89.         int op; cin >> op;
  90.         if (op == 1) {
  91.             int l,r; cin >> l >> r;
  92.             if (st.empty()) continue;
  93.             int k = *st.lower_bound(l);
  94.             int j = st.order_of_key(k);
  95.             while (k <= r) {
  96.                 int num = bit.get(k,k);
  97.                 num = d[num];
  98.                 bit.set(k,num);
  99.                 if (num == 1) st.erase(k);
  100.                 if (j+1 < st.size()) k = *st.find_by_order(++j);
  101.                 else break;
  102.             }
  103.         }
  104.         else {
  105.             int l,r; cin >> l >> r;
  106.             cout << bit.get(l,r) << endl;
  107.         }
  108.     }
  109. }
  110.  
  111.  
  112. signed main() {
  113.     fast;
  114.     Abady();
  115. }
Success #stdin #stdout 0.06s 11104KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/N2pdfq
language:
C++14 (gcc 8.3)
created:
3 hours 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!