Guest User

C

a guest
Aug 26th, 2016
259
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 10 * 1000 + 10;
  6.  
  7. typedef long long ll;
  8.  
  9. ll t_gcd[4 * N + 10];
  10. ll sum[4 * N + 10];
  11. ll add[4 * N + 10];
  12. ll a[N];
  13. ll ans[N];
  14. vector<int> id[N];
  15. vector<int> R[N];
  16.  
  17. ll gcd(ll a, ll b) {
  18.     while (b != 0) {
  19.         ll t = a;
  20.         a = b;
  21.         b = t % b;
  22.     }
  23.     return a;
  24. }
  25.  
  26. void push(int i, int l, int r) {
  27.     if (l != r) {
  28.         add[2 * i + 1] += add[i];
  29.         add[2 * i + 2] += add[i];
  30.     }
  31.     sum[i] += add[i] * (r - l + 1);
  32.     add[i] = 0;
  33. }
  34.  
  35. ll getSum(int i, int tl, int tr, int l, int r) {
  36.     push(i, tl, tr);
  37.     if (l == tl && r == tr)
  38.         return sum[i];
  39.     int m = (tl + tr) / 2;
  40.     ll sl = 0;
  41.     ll sr = 0;
  42.     if (l <= m)
  43.         sl = getSum(2 * i + 1, tl, m, l, min(r, m));
  44.     if (r > m)
  45.         sr = getSum(2 * i + 2, m + 1, tr, max(m + 1, l), r);
  46.     return sl + sr;
  47. }
  48.  
  49.  
  50. void makeAdd(int i, int tl, int tr, int l, int r, ll delta) {
  51.     push(i, tl, tr);
  52.     if (l == tl && r == tr) {
  53.         add[i] += delta;
  54.         return;
  55.     }
  56.     int m = (tl + tr) / 2;
  57.     if (l <= m)
  58.         makeAdd(2 * i + 1, tl, m, l, min(r, m), delta);
  59.     if (r > m)
  60.         makeAdd(2 * i + 2, m + 1, tr, max(m + 1, l), r, delta);
  61.     sum[i] = getSum(2 * i + 1, tl, m, tl, m) + getSum(2 * i + 2, m + 1, tr, m + 1, tr);
  62. }
  63.  
  64. void putGcd(int i, int tl, int tr, int pos, ll val) {
  65.     if (tl == tr) {
  66.         t_gcd[i] = val;
  67.         return;
  68.     }
  69.     int m = (tl + tr) / 2;
  70.     if (pos <= m)
  71.         putGcd(2 * i + 1, tl, m, pos, val);
  72.     else
  73.         putGcd(2 * i + 2, m + 1, tr, pos, val);
  74.     t_gcd[i] = gcd(t_gcd[2 * i + 1], t_gcd[2 * i + 2]);
  75. }
  76.  
  77. int getNextPos(int i, int tl, int tr, ll val) {
  78.     if (tl == tr) {
  79.         assert(t_gcd[i] % val != 0);
  80.         return tl;
  81.     }
  82.     int m = (tl + tr) / 2;
  83.     if (t_gcd[2 * i + 1] % val != 0)
  84.         return getNextPos(2 * i + 1, tl, m, val);
  85.     return getNextPos(2 * i + 2, m + 1, tr, val);
  86. }
  87.  
  88. ll getGcd(int i, int tl, int tr, int l, int r) {
  89.     if (l == tl && r == tr)
  90.         return t_gcd[i];
  91.     int m = (tl + tr) / 2;
  92.     ll gl = 0;
  93.     ll gr = 0;
  94.     if (l <= m)
  95.         gl = getGcd(2 * i + 1, tl, m, l, min(r, m));
  96.     if (r > m)
  97.         gr = getGcd(2 * i + 2, m + 1, tr, max(m + 1, l), r);
  98.     return gcd(gl, gr);
  99. }
  100.  
  101. int main() {
  102.     ios_base::sync_with_stdio(0);
  103.     int n;
  104.     cin >> n;
  105.     for (int i = 0; i < n; i++)
  106.         cin >> a[i];
  107.     int q;
  108.     cin >> q;
  109.     for (int i = 0; i < q; i++) {
  110.         int l, r;
  111.         cin >> l >> r;
  112.         l--;
  113.         r--;
  114.         R[l].push_back(r);
  115.         id[l].push_back(i);
  116.     }
  117.     for (int l = n - 1; l >= 0; l--) {
  118.         putGcd(0, 0, n - 1, l, a[l]);
  119.         ll rootGcd = t_gcd[0];
  120.         int r = l;
  121.         while (r < n) {
  122.             ll curGcd = getGcd(0, 0, n - 1, l, r);
  123.             int nextR = n;
  124.             if (curGcd != rootGcd)
  125.                 nextR = getNextPos(0, 0, n - 1, curGcd);
  126.             makeAdd(0, 0, n - 1, r, nextR - 1, curGcd);
  127.             r = nextR;
  128.         }        
  129.         for (int i = 0; i < R[l].size(); i++)
  130.             ans[id[l][i]] = getSum(0, 0, n - 1, l, R[l][i]);
  131.     }
  132.     for (int i = 0; i < q; i++)
  133.         cout << ans[i] << "\n";
  134.     return 0;
  135. }
Advertisement
Add Comment
Please, Sign In to add comment