CF914D Bash and a Tough Math Puzzle

题目链接：​​传送门​​ 问一个区间修改一个数能不能让这个区间gcd变为x；带单点修改

直接维护每个区间gcd
递归到叶子节点且%x不为0时cnt++
如果cnt>1就不行
半年前的代码了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
    int l, r, w, f;
}tree[A << 2];
int n, m, opt, a, b, c, ans, cnt, now;
int gcd(int a, int b) {
    return !b ? a : gcd(b, a % b);
}
void update(int k) {
    tree[k].w = gcd(tree[k << 1].w, tree[k << 1 | 1].w);
}
void build(int k, int l, int r) {
    tree[k].l = l;
    tree[k].r = r;
    if (l == r) {
        scanf("%d", &tree[k].w);
        return;
    }
    int m = (l + r) >> 1;
    build(k << 1, l, m);
    build(k << 1 | 1, m + 1, r);
    update(k);
}
void ask(int k) {
    if (tree[k].l == tree[k].r) {
        cnt++;
        return;
    }
    if (cnt > 1) return;
    int m = (tree[k].l + tree[k].r) >> 1;
    if (a <= m and tree[k << 1].w % c) ask(k << 1);
    if (b > m and tree[k << 1 | 1].w % c) ask(k << 1 | 1);
}
void change(int k) {
    if (tree[k].l == tree[k].r) {
        tree[k].w = b;
        return;
    }
    int m = (tree[k].l + tree[k].r) >> 1;
    if (a <= m) change(k << 1);
    else change(k << 1 | 1);
    update(k);
}

int main(int argc, char const *argv[]) {
    scanf("%d", &n); build(1, 1, n);
    scanf("%d", &m);
    while (m--) {
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d%d", &a, &b, &c);
            cnt = 0; ask(1);
            cnt > 1 ? puts("NO") : puts("YES");
        }
        else {
            scanf("%d%d", &a, &b);
            change(1);
        }
    }
    return 0;
}