fork download
  1. //It's all about what U BELIEVE
  2. #include<map>
  3. #include<set>
  4. #include<stack>
  5. #include<queue>
  6. #include<deque>
  7. #include<cmath>
  8. #include<bitset>
  9. #include<vector>
  10. #include<cstring>
  11. #include<stdio.h>
  12. #include<iostream>
  13. #include<algorithm>
  14. #define endl '\n'
  15. #define PI acos(-1)
  16. #define INF ~(1<<31)
  17. #define pb push_back
  18. #define pob pop_back
  19. #define wtm while(t--)
  20. #define wnm while(n--)
  21. #define MOD 1000000007
  22. #define lsone(Z) (Z&-Z)
  23. #define gcu getchar_unlocked
  24. #define allof(Z) Z.begin(),Z.end()
  25. #define rallof(Z) Z.rbegin(),Z.rend()
  26. #define mset(z,v) memset(z,v,sizeof(z))
  27. #define lne if(line)puts("");else line =1
  28. #define fo(s,y,z) for(int y=s ; y<(int)z ; y++)
  29. #define readf freopen("/home/ebram96/Desktop/in" , "r" , stdin);
  30. #define writef freopen("/home/ebram96/Desktop/out" , "w" , stdout);
  31. using namespace std;
  32. typedef unsigned long long ull;
  33. typedef pair<ull,ull> pairull;
  34. typedef pair<int,int> pairii;
  35. typedef vector<string> vstr;
  36. typedef deque<int> dqint;
  37. typedef set<ull> setull;
  38. typedef unsigned int ui;
  39. typedef queue<int> qint;
  40. typedef vector<int> vi;
  41. typedef set<int> seti;
  42. typedef long long ll;
  43. //int dx[]={-1,0,1, 0,-1,1, 1,-1};
  44. //int dy[]={ 0,1,0,-1, 1,1,-1,-1};
  45. const int N = 300001;
  46. ll sum[N<<2];
  47. pairii mx[N<<2]; // first = value , second = index in array
  48. int n , m , a[N] , d[1000001] , t , l , r;
  49. void calculateDivisors()
  50. {
  51. for(int i = 1 ; i < 1000001 ; i++)
  52. for(int j = i ; j < 1000001 ; j+=i)
  53. d[j]++;
  54. }
  55. void updateMax(int &i,int v,int node,int tl,int tr)
  56. {
  57. if(tl==tr)
  58. {
  59. mx[node] = {v,i};
  60. return;
  61. }
  62. int mid = (tl+tr)>>1;
  63. if(i<=mid)
  64. updateMax(i,v,node<<1,tl,mid);
  65. else
  66. updateMax(i,v,(node<<1)+1,mid+1,tr);
  67. pairii a = mx[node<<1],
  68. b = mx[(node<<1)+1];
  69. mx[node] = (a.first>b.first?a:b);
  70. }
  71. pairii getMax(int node,int &l,int &r,int tl,int tr)
  72. {
  73. if(l>tr||r<tl)
  74. return {-1,-1};
  75. if(tl>=l&&tr<=r)
  76. return mx[node];
  77. int mid = (tl+tr)>>1;
  78. pairii a = getMax(node<<1,l,r,tl,mid),
  79. b = getMax((node<<1)+1,l,r,mid+1,tr);
  80. return mx[node] = (a.first>b.first?a:b);
  81. }
  82. void updateSum(int &i,int node,int tl,int tr)
  83. {
  84. if(tl==tr)
  85. {
  86. sum[node] = a[i];
  87. return ;
  88. }
  89. int mid = (tl+tr)>>1;
  90. if(i<=mid)
  91. updateSum(i,node<<1,tl,mid);
  92. else
  93. updateSum(i,(node<<1)+1,mid+1,tr);
  94. sum[node] = sum[node<<1] + sum[(node<<1)+1];
  95. }
  96. ll getSum(int &l,int &r,int node,int tl,int tr)
  97. {
  98. if(l>tr||r<tl)
  99. return 0;
  100. if(tl>=l&&tr<=r)
  101. return sum[node];
  102. int mid = (tl+tr)>>1;
  103. return
  104. getSum(l,r,node<<1,tl,mid)+
  105. getSum(l,r,(node<<1)+1,mid+1,tr);
  106. }
  107. int main()
  108. {
  109. //readf
  110. calculateDivisors();
  111. scanf("%d %d",&n,&m);
  112. fo(1,y,n+1)
  113. {
  114. scanf("%d",&a[y]);
  115. updateMax(y,a[y],1,1,n);
  116. updateSum(y,1,1,n);
  117. }
  118. while(m--)
  119. {
  120. scanf("%d %d %d",&t,&l,&r);
  121. if(t==1)
  122. {
  123. pairii ret = getMax(1,l,r,1,n);
  124. vi tmp;
  125. while(ret.first > 2)//skip all indices with a[i] <= 2
  126. {
  127. ////set to a low value to avoid applying
  128. ////the query on the same index in the array:
  129. updateMax(ret.second,-1,1,1,n);
  130. tmp.pb(ret.second);
  131. ret = getMax(1,l,r,1,n);
  132. }
  133. int sz = tmp.size();
  134. fo(0,y,sz)
  135. {
  136. //update the array
  137. a[tmp[y]] = d[a[tmp[y]]];
  138. updateSum(tmp[y],1,1,n);
  139. updateMax(tmp[y],a[tmp[y]],1,1,n);
  140. }
  141. }
  142. else
  143. printf("%lld\n",getSum(l,r,1,1,n));
  144. }
  145. }
  146.  
Success #stdin #stdout 0.02s 39896KB
stdin
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
30
13
4
22