本文共 1993 字，大约阅读时间需要 6 分钟。
题意：
单点修改，每次询问一段l~r区间能否去掉小于等于1个数，使gcd为x
分析：
线段树。
线段树二分。如果一边的gcd不是x，那么递归这一边，找到这个位置为止，计算这样的位置的个数。
代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #define Root 1, n, 112 #define lson l, mid, rt << 113 #define rson mid + 1, r, rt << 1 | 114 #define fi(s) freopen(s,"r",stdin);15 #define fo(s) freopen(s,"w",stdout);16 using namespace std;17 typedef long long LL;18 19 inline int read() {20 int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;21 for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;22 }23 24 const int N = 500005;25 26 int gcd(int a,int b) {27 return b == 0 ? a : gcd(b, a % b);28 }29 30 int g[N << 2], G, cnt;31 32 void pushup(int rt) {33 g[rt] = gcd(g[rt << 1], g[rt << 1 | 1]);34 }35 void build(int l,int r,int rt) {36 if (l == r) {37 g[rt] = read(); return ;38 }39 int mid = (l + r) >> 1;40 build(lson), build(rson);41 pushup(rt);42 }43 void update(int l,int r,int rt,int p,int v) {44 if (l == r) {45 g[rt] = v; return ;46 }47 int mid = (l + r) >> 1;48 if (p <= mid) update(lson, p, v);49 else update(rson, p, v);50 pushup(rt);51 }52 bool query(int l,int r,int rt,int L,int R) {53 if (g[rt] % G == 0) return true; // 如果区间gcd为G的倍数，那么这个区间合法 54 if (l == r) return (++cnt) <= 1; // 否则递归下去，找到不合法的位置，计算有几个，大于1个不合法。 55 int mid = (l + r) >> 1;56 if (L > mid) query(rson, L, R);57 else if (R <= mid) query(lson, L, R);58 else return query(lson, L, R) && query(rson, L, R);59 }60 int main() {61 int n = read();62 build(Root);63 int Q = read();64 while (Q--) {65 int opt = read();66 if (opt == 1) {67 int l = read(), r = read(); G = read(); cnt = 0;68 puts(query(Root, l, r) ? "YES" : "NO");69 }70 else {71 int p = read(), v = read();72 update(Root, p, v);73 }74 }75 return 0;76 }
转载于:https://www.cnblogs.com/mjtcn/p/9735986.html