Advertisement
Ne-Biolog

Untitled

Feb 2nd, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.67 KB | None | 0 0
  1. //#include <bits/stdc++.h>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <fstream>
  5. #include <vector>
  6. #include <cmath>
  7. #include <cstdio>
  8. #include <set>
  9.  
  10. #define DEBUG 1
  11. #define TIME clock() / 1.0 / CLOCKS_PER_SEC
  12.  
  13. using namespace std;
  14.  
  15. const int N = (int)3e5 + 10;
  16.  
  17. int a[N];
  18. int n, m;
  19. int T[4 * N];
  20. set < pair <int, int> > s;
  21.  
  22. void update(int v, int l, int r, int pos, int val) {
  23. if(pos < l || pos > r)
  24. return;
  25. if(l == r) {
  26. T[v] = val;
  27. } else {
  28. int m = (l + r) >> 1;
  29. update(v * 2, l, m, pos, val);
  30. update(v * 2 + 1, m + 1, r, pos, val);
  31. T[v] = T[v * 2] + T[v * 2 + 1];
  32. }
  33.  
  34. }
  35.  
  36. int get_sum(int v, int l, int r, int tl, int tr) {
  37. if(tl > r || tr < l)
  38. return 0;
  39. if(tl >= l && tr <= r)
  40. return T[v];
  41. int tm = (tl + tr) >> 1;
  42. return get_sum(v * 2, l, r, tl, tm) + get_sum(v * 2 + 1, l, r, tm + 1, tr);
  43. }
  44.  
  45. void build(int v, int l, int r) {
  46. if(l == r) {
  47. T[v] = a[r];
  48. } else {
  49. int m = (l + r) >> 1;
  50. build(v * 2, l, m);
  51. build(v * 2 + 1, m + 1, r);
  52. T[v] = T[v * 2] + T[v * 2 + 1];
  53. }
  54. }
  55.  
  56. int get_divisors(int n) {
  57. int cnt = 0, sq = sqrt(n);
  58. for(int i = 1; i <= sq; ++i) {
  59. cnt += (n % i == 0) ? 2 : 0;
  60. }
  61. if(sq * sq == n)
  62. cnt --;
  63. return cnt;
  64. }
  65.  
  66. int main()
  67. {
  68. #if DEBUG
  69. freopen("input.txt", "r", stdin);
  70. freopen("output.txt" , "w", stdout);
  71. ios_base::sync_with_stdio(false);
  72. #endif
  73.  
  74. cin >> n >> m;
  75. for(int i = 1; i <= n; ++i) {
  76. cin >> a[i];
  77. int divisors = get_divisors(a[i]);
  78. if(a[i] != divisors) {
  79. s.insert(make_pair(i, divisors));
  80. }
  81. }
  82. build(1, 1, n);
  83.  
  84. for(int i = 0; i < m; ++i) {
  85. int type, l , r;
  86. cin >> type >> l >> r;
  87. if(type == 1) {
  88. set < pair <int, int> >:: iterator itl, itr, it;
  89. itl = s.lower_bound(make_pair(l, N));
  90. itr = s.upper_bound(make_pair(r, N));
  91. vector < pair <int, int> > rem;
  92. for(it = itl; it != itr; ++it) {
  93. pair <int, int> cur = *it;
  94. update(1, 1, n, cur.first, cur.second);
  95. int divisors = get_divisors(cur.second);
  96. if(cur.second == divisors) {
  97. rem.push_back(cur);
  98. }
  99. }
  100. if(rem.size() != 0) {
  101. for(int j = 0; j < rem.size(); ++j) {
  102. s.erase(rem[i]);
  103. }
  104. }
  105.  
  106. } else {
  107. cout << get_sum(1, l, r, 1, n) << '\n';
  108. }
  109. }
  110.  
  111. return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement