fork(1) download
copy 
  1. //#pragma GCC optimize("O3, unroll-loops")
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define ll long long
  6. #define ull unsigned long long 
  7. #define fr(n) for(ll i = 0; i < n; i++)
  8. #define rep(i,a,b) for(int i = a; i < b; i++)
  9. #define vll vector<pair<ll,ll>>
  10. #define vii vector<pair<int,int>>
  11. #define pi acos(-1)
  12. #define all(v) (v).begin(),(v).end()
  13. #define mp make_pair
  14. #define print(a) for(auto x:(a))cout << x <<  
  15. #define ios ios::sync_with_stdio(0);cin.tie(0);
  16. #define endl "\n"
  17. #define INF (ll)1e15
  18. #define int ll
  19. using namespace std;
  20.  
  21.  
  22. const int MAXN = 1e6 + 5;
  23.  
  24.  
  25. int arr[MAXN];
  26.  
  27.  
  28. vector<int> D(MAXN, 1);
  29.  
  30. void precompute_D() {
  31.     for (int i = 2; i < MAXN; ++i) {
  32.         for (int j = i; j < MAXN; j += i) {
  33.             D[j]++;
  34.         }
  35.     }
  36. }
  37.  
  38. class FenwickTree {
  39.     vector<int> bit;
  40.     int n;
  41.  
  42. public:
  43.     FenwickTree(int size) : n(size), bit(size + 1, 0) {}
  44.  
  45.     void update(int index, int delta) {
  46.         for (++index; index <= n; index += index & -index)
  47.             bit[index] += delta;
  48.     }
  49.  
  50.     int query(int index) {
  51.         int sum = 0;
  52.         for (++index; index > 0; index -= index & -index)
  53.             sum += bit[index];
  54.         return sum;
  55.     }
  56.  
  57.     int rangeQuery(int left, int right) {
  58.         return query(right) - query(left - 1);
  59.     }
  60. };
  61.  
  62. void solve(){
  63.     int N, Q; cin >> N >> Q;
  64.     FenwickTree fenwick(N);
  65.     map<int,int> alive;
  66.     rep(i,0,N){
  67.     	cin >> arr[i];
  68.     	fenwick.update(i,arr[i]);
  69.     	if(arr[i]>2) alive.emplace_hint(alive.end(),i,arr[i]);
  70.     }
  71.  
  72.     while(Q--){
  73.         int t; cin >> t;
  74.         int l, r; cin >> l >> r;
  75.         l--; r--;
  76.  
  77.         if(t==1){
  78.             auto it = alive.lower_bound(l);
  79.             while(it!=alive.end()&&it->first<=r){
  80.             	auto nxt = it;++nxt;
  81.  
  82.             	int x = it->second;
  83.             	int xnew = D[x];
  84.             	fenwick.update(it->first, xnew-x);
  85.  
  86.             	if(xnew>2) it->second = xnew;
  87.             	else alive.erase(it);
  88.             	it = nxt;
  89.             }
  90.         }else {
  91.             cout << fenwick.rangeQuery(l, r) << endl;
  92.         }
  93.     }
  94. }
  95.  
  96.  
  97.  
  98. int32_t main() {
  99.     ios
  100.     int t = 1;
  101.     precompute_D();
  102.     //cin >> t;
  103.     while(t--)solve();
  104.  
  105.     return 0;
  106. }
Success #stdin #stdout 0.07s 11160KB
comments (?)
stdin
copy 
7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7
stdout
copy 
30
13
4
22
https://ideone.com/ln2qC8
language:
C++14 (gcc 8.3)
created:
8 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!