Guest User

Untitled

a guest
Dec 1st, 2016
279
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX_N = 300001;
  6. const int k = 400;
  7.  
  8. struct sqrt_decomposition {
  9.     long long a[MAX_N];
  10.     long long b[MAX_N / k + 1];
  11.     int div_k[MAX_N];
  12.     vector<vector<int>> divisors;
  13.     int n;
  14.  
  15.     sqrt_decomposition(int n1) {
  16.         n = n1;
  17.         divisors.assign(n, vector<int>());
  18.         for (int i = 1; i < n; i++) {
  19.             div_k[i] = i / k;
  20.             for (long long j = 1; j * j <= i; j++) {
  21.                 if (i % j == 0) {
  22.                     divisors[i].push_back(j);
  23.                     if (j * j != i) divisors[i].push_back(i / j);
  24.                 }
  25.             }
  26.         }
  27.         for (int i = 0; i < n; i++) a[i] = 0;
  28.         for (int i = 0; i < n / k + 1; i++) b[i] = 0;
  29.     }
  30.  
  31.     void add(int l, int r, int x) {
  32.         int bl = div_k[l];
  33.         int br = div_k[r];
  34.         if (bl == br) {
  35.             for (int i = l; i <= r; i++) {
  36.                 a[i] += x;
  37.             }
  38.         } else {
  39.             for (int i = l; i < (bl + 1) * k; i++) {
  40.                 a[i] += x;
  41.             }
  42.             for (int i = br * k; i <= r; i++) {
  43.                 a[i] += x;
  44.             }
  45.             for (int i = bl + 1; i <= br - 1; i++) {
  46.                 b[i] += x;
  47.             }
  48.         }
  49.     }
  50.  
  51.     long long get(int i) {
  52.         int bl = div_k[i];
  53.         return a[i] + b[bl];
  54.     }
  55.  
  56.     long long get_power(int i) {
  57.         long long ans = 0;
  58.         for (int j : divisors[i]) {
  59.             ans += get(j);
  60.         }
  61.         return ans;
  62.     }
  63. };
  64.  
  65. int main()
  66. {
  67.     ios_base::sync_with_stdio(false);
  68.     cin.tie(0);
  69.     cout.tie(0);
  70.     int n;
  71.     cin >> n;
  72.     int a[n + 1];
  73.     int inp;
  74.     for (int i = 1; i <= n; i++) {
  75.         cin >> inp;
  76.         a[i] = inp;
  77.     }
  78.     sqrt_decomposition sd(n + 1);
  79.     int q;
  80.     cin >> q;
  81.     int t, l, r, d;
  82.     for (int i = 0; i < q; i++) {
  83.         cin >> t;
  84.         if (t == 1) {
  85.             cin >> l;
  86.             cout << sd.get_power(l) + a[l] << '\n';
  87.         } else {
  88.             cin >> l >> r >> d;
  89.             sd.add(l, r, d);
  90.         }
  91.     }
  92. }
Advertisement
Add Comment
Please, Sign In to add comment