914D - Bash and a Tough Math Puzzle - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define ld long double
#define OK(x) cout<<(x?"YES\n":"NO\n")
#define ok(x) cout<<(x?"yes\n":"no\n")
#define Ok(x) cout<<(x?"Yes\n":"No\n")
#define lp(n) for(ll i = 0; i < (n); ++i)
#define lp1(n) for(ll i = 1; i <= (n); ++i)
#define watch(num) cout<< #num <<": "<< num << "\n";
#define watchV(v) cout<< #v <<": "; for(auto i:v) cout << i << " ";
#define en '\n'
#define Endl '\n'
#define endl '\n'
#define al(n) n.begin(), n.end()
#define all(n) n.rbegin(), n.rend()
#define GRAPH vector<vector<int>>
const ll MOD = 1000000007;
const ll OO = INT32_MAX;
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define tc ll testcase;cin>>testcase;while(testcase--)

template<typename T>
istream &operator>>(istream &input, vector<T> &data) {
    for (T &x: data)input >> x;
    return input;
}

template<typename T>
ostream &operator<<(ostream &output, const vector<T> &data) {
    for (const T &x: data)output << x << " ";
    return output;
}

int numOfDigits(ll num) {
    return 1 + floor(log10(num));
}

ll tree_SZ = 1e5 + 5;
vector<ll> arr, tree;

void build_tree(ll node, ll left, ll right) {
    if (left == right) {
        tree[node] = arr[left];
        return;
    }
    ll mid = (left + right) / 2;

    build_tree(2 * node, left, mid);
    build_tree((2 * node) + 1, mid + 1, right);

    tree[node] = __gcd(tree[2 * node], tree[(2 * node) + 1]);

}

void update_tree(ll node, ll left, ll right, ll idx, ll val) {
    if (idx > right || idx < left)return;

    if (left == right) {
        tree[node] = val;
        return;
    }

    ll mid = (left + right) / 2;
    update_tree(2 * node, left, mid, idx, val);
    update_tree((2 * node) + 1, mid + 1, right, idx, val);

    tree[node] = __gcd(tree[2 * node], tree[(2 * node) + 1]);
}

int cnt;

void query(ll node, ll left, ll right, ll l, ll r, ll gcd) {
    if (r < left || l > right)return;
    if (l <= left && r >= right) {
        if (!(tree[node] % gcd))return;
        else {
            if (left == right) {
                cnt++;
                return;
            }
        }
    }

    ll mid = (left + right) / 2;
    query(2 * node, left, mid, l, r, gcd);
    if (cnt > 1)return;
    query((2 * node) + 1, mid + 1, right, l, r, gcd);
    if (cnt > 1)return;

}


void solve() {
    cin >> tree_SZ;
    tree.resize(4 * tree_SZ);
    arr.resize(tree_SZ + 1, 0);
    for (int i = 1; i <= tree_SZ; i++)cin >> arr[i];
    build_tree(1, 1, tree_SZ);
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        if (x == 1) {
            int l, r, g;
            cin >> l >> r >> g;
            cnt = 0;
            query(1, 1, tree_SZ, l, r, g);
            OK(cnt <= 1);
        } else {
            int idx, val;
            cin >> idx >> val;
            update_tree(1, 1, tree_SZ, idx, val);
        }
    }

}

int main() {

    speed

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

//    tc
    solve();
    return 0;
}