fork download
copy 
  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
comments (?)
stdin
copy 
6
1 2 1 4 5 6
5
2 2 4 2
1 3
1 4
2 3 5 1
1 5
stdout
copy 
3
8
6
https://ideone.com/7PE9ll
language:
C++14 (gcc 8.3)
created:
7 years 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!