Guest User

Untitled

a guest
Feb 4th, 2018
364
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define x first
  6. #define y second
  7. #define mp make_pair
  8. #define pb push_back
  9. #define sqr(a) ((a) * (a))
  10. #define sz(a) int(a.size())
  11. #define all(a) a.begin(), a.end()
  12. #define forn(i, n) for(int i = 0; i < int(n); i++)
  13. #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
  14.  
  15. typedef long long li;
  16. typedef long double ld;
  17. typedef pair<int, int> pt;
  18.  
  19. template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
  20. return out << "(" << a.x << ", " << a.y << ")";
  21. }
  22.  
  23. template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
  24. out << "[";
  25. forn(i, sz(v)) {
  26. if(i) out << ", ";
  27. out << v[i];
  28. }
  29. return out << "]";
  30. }
  31.  
  32. mt19937 rnd(time(NULL));
  33.  
  34. const int INF = int(1e9);
  35. const li INF64 = li(1e18);
  36. const int MOD = INF + 7;
  37. const ld EPS = 1e-9;
  38. const ld PI = acos(-1.0);
  39.  
  40. const int N = 300 * 1000 + 13;
  41. const int M = 1000 * 1000 + 13;
  42.  
  43. int n, m;
  44. int a[N];
  45. li sum[4 * N];
  46. int mx[4 * N];
  47. int f[M];
  48. int d[M];
  49.  
  50. bool read () {
  51. if (scanf("%d%d", &n, &m) != 2)
  52. return false;
  53. forn(i, n) scanf("%d", &a[i]);
  54. return true;
  55. }
  56.  
  57. void init() {
  58. for (int i = 2; i < M; i++) {
  59. if (d[i]) continue;
  60. d[i] = i;
  61. for (li j = i * 1ll * i; j < M; j += i)
  62. if (!d[j]) d[j] = i;
  63. }
  64.  
  65. f[1] = 1;
  66. for (int i = 2; i < M; i++) {
  67. int lst = -1, cnt = 0;
  68. int x = i;
  69. f[i] = 1;
  70. while (x > 1) {
  71. if (lst != d[x]) {
  72. f[i] *= cnt + 1;
  73. lst = d[x];
  74. cnt = 1;
  75. } else {
  76. cnt++;
  77. }
  78. x /= d[x];
  79. }
  80.  
  81. f[i] *= cnt + 1;
  82. }
  83. }
  84.  
  85. void build(int v, int l, int r) {
  86. if (l == r) {
  87. sum[v] = mx[v] = a[l];
  88. return;
  89. }
  90. int mid = (l + r) >> 1;
  91. build(v * 2 + 1, l, mid);
  92. build(v * 2 + 2, mid + 1, r);
  93. sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
  94. mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
  95. }
  96.  
  97. void upd(int v, int l, int r, int L, int R) {
  98. if (l == r) {
  99. sum[v] = mx[v] = a[l] = f[a[l]];
  100. return;
  101. }
  102. int mid = (l + r) >> 1;
  103. if (L <= mid && mx[v * 2 + 1] > 2) upd(v * 2 + 1, l, mid, L, min(mid, R));
  104. if (R > mid && mx[v * 2 + 2] > 2) upd(v * 2 + 2, mid + 1, r, max(mid + 1, L), R);
  105. sum[v] = sum[v * 2 + 1] + sum[v * 2 + 2];
  106. mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
  107. }
  108.  
  109. li get(int v, int l, int r, int L, int R) {
  110. if (L > R) return 0;
  111. if (l == L && r == R) return sum[v];
  112. int mid = (l + r) >> 1;
  113. return get(v * 2 + 1, l, mid, L, min(mid, R)) + get(v * 2 + 2, mid + 1, r, max(mid + 1, L), R);
  114. }
  115.  
  116. void solve() {
  117. init();
  118. build(0, 0, n - 1);
  119.  
  120. forn(_, m) {
  121. int t, l, r;
  122. scanf("%d%d%d", &t, &l, &r);
  123. if (t == 1) upd(0, 0, n - 1, l - 1, r - 1);
  124. else printf("%lld\n", get(0, 0, n - 1, l - 1, r - 1));
  125. }
  126. }
  127.  
  128. int main() {
  129. #ifdef _DEBUG
  130. freopen("input.txt", "r", stdin);
  131. // freopen("output.txt", "w", stdout);
  132.  
  133. int tt = clock();
  134.  
  135. #endif
  136.  
  137. cerr.precision(15);
  138. cout.precision(15);
  139. cerr << fixed;
  140. cout << fixed;
  141.  
  142. while(read()) {
  143. solve();
  144.  
  145. #ifdef _DEBUG
  146. cerr << "TIME = " << clock() - tt << endl;
  147. tt = clock();
  148. #endif
  149.  
  150. }
  151. }
RAW Paste Data