CF914D Bash and a Tough Math Puzzle [线段树]

CF914D Bash and a Tough Math Puzzle [线段树]

​​传送门​​

如果区间的gcd不是x的倍数, 就暴力向下找, 如果个数 > 1, 就可以不用找了, 并且输出 NO

这样最多向下找两次, 复杂度是正确的

#include#define N 500050using namespace std;int read(){ int x; scanf("%d", &x); return x;}int val[N<<2], a[N], n, m, cnt;int gcd(int a, int b){ return !b ? a : gcd(b, a % b);}void Pushup(int x){ val[x] = gcd(val[x<<1], val[x<<1|1]);}void Build(int x, int l, int r){ if(l == r){ val[x] = a[l]; return;} int mid = (l+r) >> 1; Build(x<<1, l, mid); Build(x<<1|1, mid+1, r); Pushup(x);}void Modify(int x, int l, int r, int pos, int v){ if(l == r){ val[x] = v; return;} int mid = (l+r) >> 1; if(pos <= mid) Modify(x<<1, l, mid, pos, v); else Modify(x<<1|1, mid+1, r, pos, v); Pushup(x);}void Quary(int x, int l, int r, int L, int R, int v){ if(cnt > 1) return; if(l == r){ cnt++; return;} int mid = (l+r) >> 1; if(L<=mid && val[x<<1] % v) Quary(x<<1, l, mid, L, R, v); if(R>mid && val[x<<1|1] % v) Quary(x<<1|1, mid+1, r, L, R, v);}int main(){ n = read(); for(int i=1; i<=n; i++) a[i] = read(); Build(1, 1, n); m = read(); while(m--){ int op = read(); if(op == 1){ int l = read(), r = read(), x = read(); cnt = 0; Quary(1, 1, n, l, r, x); if(cnt <= 1) printf("YES\n"); else printf("NO\n"); } if(op == 2){ int p = read(), v = read(); Modify(1, 1, n, p, v); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。