fork download
  1. #include <cstdio>
  2. #include <cctype>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. constexpr int kMaxN = 300000 + 1;
  7. constexpr int kBuffSize = 4096;
  8. constexpr int NIL = -1;
  9.  
  10. int foo[kMaxN];
  11. long long tree[kMaxN];
  12.  
  13. struct List {
  14. int divisor;
  15. int next;
  16. } buff[kMaxN * 20];
  17.  
  18. int head[kMaxN];
  19.  
  20. inline char get_char() {
  21. static char buff[kBuffSize];
  22. static int pos = kBuffSize;
  23. if (pos == kBuffSize) {
  24. fread(buff, 1, kBuffSize, stdin);
  25. pos = 0;
  26. }
  27. return buff[pos++];
  28. }
  29.  
  30. inline int read_int() {
  31. int q = 0;
  32. char c;
  33. do {
  34. c = get_char();
  35. } while (not isdigit(c));
  36. do {
  37. q = (q << 1) + (q << 3) + (c - '0');
  38. c = get_char();
  39. } while (isdigit(c));
  40. return q;
  41. }
  42.  
  43. void fenwick_update(const int position, const int m_size,
  44. const int delta) {
  45. for (int i = position; i <= m_size; i += (i & -i)) {
  46. tree[i] += delta;
  47. }
  48. }
  49.  
  50. long long fenwick_query(const int position) {
  51. long long ret = 0LL;
  52. for (int i = position; i > 0; i -= (i & -i)) {
  53. ret += tree[i];
  54. }
  55. return ret;
  56. }
  57.  
  58. void get_divisors(const int n) {
  59. int buff_size = 0;
  60. memset(head + 1, NIL, 4 * n);
  61. for (int i = 1; i <= n; i += 1) {
  62. for (int j = i; j <= n; j += i) {
  63. buff[buff_size].divisor = i;
  64. buff[buff_size].next = head[j];
  65. head[j] = buff_size++;
  66. }
  67. }
  68. }
  69.  
  70. int main() {
  71. int n = read_int();
  72. for (int i = 1; i <= n; i += 1) {
  73. foo[i] = read_int();
  74. }
  75.  
  76. get_divisors(n);
  77.  
  78. int q = read_int();
  79. for (int iter = 0; iter < q; iter += 1) {
  80. int op_type = read_int();
  81. if (op_type == 2) {
  82. int lo = read_int(), hi = read_int(), delta = read_int();
  83. fenwick_update(lo, n, delta);
  84. fenwick_update(hi + 1, n, -delta);
  85. } else {
  86. int pos = read_int();
  87. long long ret = foo[pos];
  88. for (int i = head[pos]; i != NIL; i = buff[i].next) {
  89. ret += fenwick_query(buff[i].divisor);
  90. }
  91. printf("%lld\n", ret);
  92. }
  93. }
  94. return 0;
  95. }
Success #stdin #stdout 0s 55040KB
stdin
6
1 2 1 4 5 6
5
2 2 4 2
1 3
1 4
2 3 5 1
1 5
stdout
3
8
6