Advertisement
Ginger_samurai

Untitled

Oct 13th, 2020
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.46 KB | None | 0 0
  1. #include<vector>
  2. #include <string>
  3. #include<algorithm>
  4. #include <iostream>
  5. #include <queue>
  6. #include<set>
  7. #include<stack>
  8. #include<cmath>
  9. #include<math.h>
  10. #include<map>
  11. #include<unordered_map>
  12. #include<unordered_map>
  13. #include<ext/rope>
  14. using namespace std;
  15. using namespace __gnu_cxx;
  16. typedef long long ll;
  17. typedef pair<long long, long long> pll;
  18. #define mp make_pair
  19. #define fi(b, c) for(auto i = b; i <= c; i++)
  20. #define fj(b, c) for(auto j = b; j <= c; j++)
  21. #define fk(b, c) for(auto k = b; k <= c; k++)
  22. #define fq(b, c) for(auto q = b; q <= c; q++)
  23. #define fw(b, c) for(auto w = b; w <= c; w++)
  24. #define fim(b, c) for(auto i = b; i >= c; i--)
  25. #define fjm(b, c) for(auto j = b; j >= c; j--)
  26. #define fkm(b, c) for(auto k = b; k >= c; k--)
  27. #define all(a) a.begin(), a.end()
  28. #define rall(a) a.rbegin(), a.rend()
  29. #define sz(a) (ll)(a.size())
  30. #define fs first
  31. #define sd second
  32. #define endl "\n"
  33. #define cin(a) for(ll o = 0; o<a.size(); o++) cin>>a[o];
  34. #define cout(a) for(ll o = 0; o<a.size(); o++) cout<<a[o]<<" ";
  35. const ll inf = 1e9 + 123, llinf = 1e18 + 123;
  36. void xru(){
  37. //  setlocale(LC_ALL, "rus");
  38. //  freopen(".in", "r", stdin);
  39. //  freopen(".out", "w", stdout);
  40. //  ios_base::sync_with_stdio(false);
  41. //  cin.tie(NULL);
  42. //  cout.tie(NULL);
  43. }
  44. void run(){
  45.     cout<<endl;
  46.     system("pause");
  47. }
  48. ll MAXV = 1e5 + 123;
  49. ll n;
  50. vector<ll>t(4*MAXV), a(4*MAXV);
  51.  
  52. ll gcd(ll a, ll b){
  53.     if (b == 0) return a;
  54.     return gcd (b, a % b);
  55. }
  56.  
  57. ll left_son(ll v){ return 2 * v + 1; };
  58. ll right_son(ll v){ return 2 * v + 2; };
  59.  
  60. void push(ll v, ll L, ll R){
  61.     t[v] += a[v] * (R - L);
  62.     a[left_son(v)] += a[v];
  63.     a[right_son(v)] += a[v];
  64.     a[v] = 0;
  65. }
  66.  
  67. void relax(ll v, ll L, ll M, ll R){
  68.     t[v] = gcd(t[left_son(v)] +  a[left_son(v)] * (M - L),
  69.            t[right_son(v)] + a[right_son(v)] * (R - M));
  70. }
  71.  
  72. void build(vector<ll>& base, ll v = 0, ll L = 0, ll R = n){
  73.     // cout << L << " " << R << endl;
  74.     a[v] = 0;
  75.     if(R - L == 1){
  76.         t[v] = base[L];
  77.         return;
  78.     }
  79.     ll M = (L + R) / 2;
  80.     build(base, left_son(v), L, M);
  81.     build(base, right_son(v), M, R);
  82.     relax(v, L, M, R);
  83.     return;
  84. }
  85.  
  86. void add(ll l, ll r, ll h, ll v = 0, ll L = 0, ll R = n){
  87.     // cout << L << " " << R << endl;
  88.     if( L >= l && R <= r){
  89.         a[v] += h;
  90.         return;
  91.     }
  92.     else if(L >= r || R <= l){
  93.         return;
  94.     }
  95.     push(v, L, R);
  96.     ll M = (L + R)/2;
  97.     add(l, r, h, left_son(v), L, M);
  98.     add(l, r, h, right_son(v), M, R);
  99.     relax(v, L, M, R);
  100. }
  101.  
  102. ll sum(ll l, ll r, ll v = 0, ll L = 0, ll R = n){
  103.     // cout << L << " " << R << endl;
  104.     if(L >= l && R <= r) {
  105.         return t[v] + a[v] * (R-L);
  106.     }
  107.     if(L >= r || R <= l){
  108.         return 0;
  109.     }
  110.     push(v, L, R);
  111.     ll M = (L+R)/2;
  112.     ll ans = gcd(sum(l, r, left_son(v), L, M), sum(l, r, right_son(v), M, R));
  113.     relax(v, L, M, R);
  114.     return ans;
  115. }
  116.  
  117. void print_tree(ll agg = 0, ll v = 0, ll L = 0, ll R = n){
  118.     agg += a[v];
  119.     if(R - L == 1){
  120.         cout << L <<": " << t[v] + agg << endl;
  121.         return;
  122.     }
  123.     cout << "[" << L << " " << R << ")" << t[v] << endl;
  124.     ll M =(L+R)/2;
  125.     print_tree(agg, left_son(v), L, M);
  126.     print_tree(agg, right_son(v), M, R);
  127. }
  128.  
  129. int main() {
  130.     cin >> n;
  131.     vector<ll> base(n);
  132.     cin (base);
  133.     build(base);
  134.     ll q;
  135.     cin >> q;
  136.     fi(0, q-1){
  137.         ll l, r;
  138.         cin >> l >> r;
  139.         cout << sum(l-1, r) << endl;
  140.     }
  141.     // print_tree();
  142.     run();
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement