bhupixb

Sement tree GCD from L to R

Jul 24th, 2018
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.63 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. typedef long long int ll;
  4. const int N = 2e6;
  5. ll arr[N], tree[N], level;
  6. #define C(x) cout << x << ' '
  7. #define L '\n'
  8. void build(ll start, ll endd, ll seg_tree_index){
  9.  
  10. if(start == endd){
  11. tree[seg_tree_index] = arr[start];
  12. return ;
  13. }
  14. ll mid = (start + endd) >> 1;
  15. build(start, mid, 2 * seg_tree_index);
  16. build(mid + 1, endd, 2 * seg_tree_index + 1);
  17.  
  18. tree[seg_tree_index] = __gcd(tree[2 * seg_tree_index], tree[2 * seg_tree_index + 1]);
  19. }
  20.  
  21. int query(int l, int r, int ql, int qr, int seg_tree_index){
  22. // C(l);C(r);C(ql);C(qr);C(L);
  23. if(r < ql || l > qr)return 0;
  24. if(ql <= l && qr >= r)return tree[seg_tree_index];
  25. int mid = (l+r) >> 1;
  26. return __gcd(query(l, mid, ql, qr, 2 * seg_tree_index), query(mid + 1, r, ql, qr, 2 * seg_tree_index + 1));
  27. }
  28.  
  29. /*
  30. void update(ll l, ll r,ll pos, ll val, ll seg_tree_index, ll fl){
  31. if(l <= pos && r >= pos){ // Think some other way after AC bout this condition
  32. if(l == r && l == pos){
  33. tree[seg_tree_index] = val;
  34. return;
  35. }
  36. ll mid = (l + r) >> 1;
  37. update(l, mid, pos, val, 2 * seg_tree_index, fl );
  38. update(mid + 1, r, pos, val, 2 * seg_tree_index + 1, fl );
  39. }
  40. else
  41. return;
  42. }*/
  43. int main(){
  44. ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  45. ll n, i, q, ql, qr;
  46. cin >> n;// >> q;
  47. for(i = 1; i <= n; i++)
  48. cin >> arr[i];
  49.  
  50. build(1, n, 1);
  51.  
  52. //for(i = 1; tree[i]; i++)
  53. // cout << tree[i] << ' ';
  54. cout << endl;
  55. cout << query(1, n, 1, 2, 1);
  56.  
  57.  
  58. return 0;
  59. }
Add Comment
Please, Sign In to add comment