HDU 4777 Rabbit Kingdom(树状数组离线处理) 数据结构-树状数组

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4777
题目大意: 一个兔子王国，有N只兔子，每只兔子有一个重量，如果两只兔子的重量不互质，那么就会干架，现在国王想将l r之间的兔子关进监狱，它想知道会有多少只兔子不会和别的兔子干架。也就是求l到r这个区间内有多少个数与所有数都互质

题目解析: 这题的思路真感觉是山路十八弯呀。后面学习了kuangbin大大的题解，才懂得怎么处理后面。
题目要求判断l到r内有多少个数与所有数都互质，那么我们可以求反面就是l，r内与其他数不互质的个数，可以想到先求每一个数num[i]到其左边和右边第一个与其不互质的数的我位置l[i],r[i]。=》这里我们可以预处理，通过求出每一个数的因子，然后标记每一个因子的最大的位置，来求出某个数的因子中因子坐标最大的位置，即为l[i]。对于r[i]则正好相反。

然后就是处理询问，将询问按照右区间排序，碰到i，则L位置+1，碰到R，则i位置+1，L位置-1。（如果L ≤ l && r ≤ R，那么兔子在这个l，r询问中是不会与其他兔子冲突）
这样l~r区间统计的即为会打架的兔子。

#include #include #include #include #include using namespace std; const int maxn = 200020; vectorV[maxn]; vectorvec[maxn]; int num[maxn]; int l[maxn], r[maxn]; int Hash1[maxn]; int Hash2[maxn]; struct Node { int l, r, index; }query[maxn]; void init() { for(int i = 2; i <= 200010; i++) for(int j=i; j<200010; j+=i) V[j].push_back(i); }int cmp(Node a, Node b) { if(a.r == b.r) return a.l < b.l; return a.r < b.r; } int c[maxn], a[maxn]; int lowbit(int x) { return x & -x; }int sum(int x) { int ret = 0; while(x > 0) { ret += c[x]; x -= lowbit(x); } return ret; }void add(int x, int d) { if(!x) return ; while(x < maxn) { c[x] += d; x += lowbit(x); } }int ans[maxn]; int main () { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int n, m; init(); while(scanf("%d %d", &n, &m), n&&m) { memset(Hash1, 0, sizeof(Hash1)); memset(Hash2, 0x3f, sizeof(Hash2)); for(int i = 1; i <= n; i++) { scanf("%d", &num[i]); int Min = 0; for(int j = 0; j < V[num[i]].size(); j++) { int tmp = V[num[i]][j]; Min = max(Hash1[tmp], Min); Hash1[tmp] = max(Hash1[tmp], i); } l[i] = Min; }for(int i = n; i >= 1; i--) { int Max = n+1; for(int j = 0; j < V[num[i]].size(); j++) { int tmp =V[num[i]][j]; Max = min(Hash2[tmp], Max); Hash2[tmp] = min(Hash2[tmp], i); } r[i] = Max; }//for(int i = 1; i <= n; i++) //printf("l[%d] = %d, r[%d] = %d\n", i,l[i],i,r[i]); for(int i = 1; i <= m; i++) { scanf("%d %d", &query[i].l, &query[i].r); query[i].index = i; }sort(query+1, query+m+1, cmp); memset(c, 0, sizeof(c)); for(int i = 1; i <= n; i++) vec[i].clear(); for(int i = 1; i <= n; i++)vec[r[i]].push_back(i); int id = 1; for(int i = 1; i <= m; i++) { while(id <= n && id <= query[i].r) { add(l[id]+1, 1); inttmp = vec[id].size(); for(int j = 0; j < tmp; j++) { int v = vec[id][j]; add(l[v]+1, -1); add(v+1, 1); } id++; } ans[query[i].index] = query[i].r - query[i].l + 1 - (sum(query[i].r+1) - sum(query[i].l-1+1)); } for(int i = 1; i <= m; i++) printf("%d\n", ans[i]); } return 0; }

【HDU 4777 Rabbit Kingdom(树状数组离线处理)】