pushup函数写成lson.mins < rson.cnt,于是我又以WA屠版了。。。T^T
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <algorithm> #include <map> using namespace std; const int maxn = 100010; int s[maxn]; int n, t; template <class T> char scanf(T *x) { (*x) = 0; char ch = getchar(); while(ch < '0' || ch > '9') { ch = getchar(); if(ch == EOF) return EOF; } while(ch >= '0' && ch <= '9') { (*x) *= 10; (*x) += ch - '0'; ch = getchar(); } return ch; } struct Node { int gcd, mins, cnt; Node(int _g = 0, int _m = 0, int _c = 0): gcd(_g), mins(_m), cnt(_c) {} void out() { printf("%d %d %d\n", gcd, mins, cnt); } }nn[maxn << 2]; inline int GCD(int x, int y) { return y == 0 ? x : GCD(y, x % y); } Node pushup(const Node &lson, const Node &rson) { Node ret; ret.gcd = GCD(lson.gcd, rson.gcd); ret.mins = min(lson.mins, rson.mins); if(lson.mins == rson.mins) ret.cnt = lson.cnt + rson.cnt; else if(lson.mins < rson.mins) ret.cnt = lson.cnt; else ret.cnt = rson.cnt; return ret; } void build(int l = 1, int r = n, int rt = 1) { if(l == r) { scanf(&s[l]); nn[rt].gcd = s[l]; nn[rt].mins = s[l]; nn[rt].cnt = 1; return ; } int m = (l + r) >> 1; build(l, m, rt << 1); build(m + 1, r, rt << 1 | 1); nn[rt] = pushup(nn[rt << 1], nn[rt << 1 | 1]); } Node query(int L, int R, int l = 1, int r = n, int rt = 1) { if(L <= l && R >= r) return nn[rt]; int m = (l + r) >> 1; Node lson, rson; if(L <= m) lson = query(L, R, l, m, rt << 1); if(R > m) rson = query(L, R, m + 1, r, rt << 1 | 1); if(lson.gcd && rson.gcd) return pushup(lson, rson); else if(lson.gcd) return lson; else return rson; } int main() { // freopen("F.in", "r", stdin); int l, r; while(~scanf(&n)) { build(); scanf(&t); while(t--) { scanf(&l); scanf(&r); int ans = r - l + 1; Node cache = query(l, r); // cache.out(); if(cache.gcd == cache.mins) ans -= cache.cnt; printf("%d\n", ans); } } return 0; }