D. Bash and a Tough Math Puzzle
http://codeforces.com/contest/914/problem/D
题意：
单点修改，每次询问一段l~r区间能否去掉小于等于1个数，使gcd为x
分析：
线段树。
线段树二分。如果一边的gcd不是x，那么递归这一边，找到这个位置为止，计算这样的位置的个数。
代码：
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 #include<iostream> 6 #include<cctype> 7 #include<set> 8 #include<vector> 9 #include<queue> 10 #include<map> 11 #define Root 1, n, 1 12 #define lson l, mid, rt << 1 13 #define rson mid + 1, r, rt << 1 | 1 14 #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 }