Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- typedef long long int ll;
- const int N = 2e6;
- ll arr[N], tree[N], level;
- #define C(x) cout << x << ' '
- #define L '\n'
- void build(ll start, ll endd, ll seg_tree_index){
- if(start == endd){
- tree[seg_tree_index] = arr[start];
- return ;
- }
- ll mid = (start + endd) >> 1;
- build(start, mid, 2 * seg_tree_index);
- build(mid + 1, endd, 2 * seg_tree_index + 1);
- tree[seg_tree_index] = __gcd(tree[2 * seg_tree_index], tree[2 * seg_tree_index + 1]);
- }
- int query(int l, int r, int ql, int qr, int seg_tree_index){
- // C(l);C(r);C(ql);C(qr);C(L);
- if(r < ql || l > qr)return 0;
- if(ql <= l && qr >= r)return tree[seg_tree_index];
- int mid = (l+r) >> 1;
- return __gcd(query(l, mid, ql, qr, 2 * seg_tree_index), query(mid + 1, r, ql, qr, 2 * seg_tree_index + 1));
- }
- /*
- void update(ll l, ll r,ll pos, ll val, ll seg_tree_index, ll fl){
- if(l <= pos && r >= pos){ // Think some other way after AC bout this condition
- if(l == r && l == pos){
- tree[seg_tree_index] = val;
- return;
- }
- ll mid = (l + r) >> 1;
- update(l, mid, pos, val, 2 * seg_tree_index, fl );
- update(mid + 1, r, pos, val, 2 * seg_tree_index + 1, fl );
- }
- else
- return;
- }*/
- int main(){
- ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
- ll n, i, q, ql, qr;
- cin >> n;// >> q;
- for(i = 1; i <= n; i++)
- cin >> arr[i];
- build(1, n, 1);
- //for(i = 1; tree[i]; i++)
- // cout << tree[i] << ' ';
- cout << endl;
- cout << query(1, n, 1, 2, 1);
- return 0;
- }
Add Comment
Please, Sign In to add comment