---

title: HDU-4777 Rabbit Kingdomom(樹狀數(shù)組、區(qū)間離線)
date: 2018-12-14 11:20:15
tags: [樹狀數(shù)組,離線,區(qū)間]
categories: ACM

題目鏈接

Problem Description

Long long ago, there was an ancient rabbit kingdom in the forest. Every rabbit in this kingdom was not cute but totally pugnacious, so the kingdom was in chaos in season and out of season.
　　n rabbits were numbered form 1 to n. All rabbits’ weight is an integer. For some unknown reason, two rabbits would fight each other if and only if their weight is NOT co-prime.
　　Now the king had arranged the n rabbits in a line ordered by their numbers. The king planned to send some rabbits into prison. He wanted to know that, if he sent all rabbits between the i-th one and the j-th one(including the i-th one and the j-th one) into prison, how many rabbits in the prison would not fight with others.
　　Please note that a rabbit would not fight with himself.

Input

The input consists of several test cases.
　　The first line of each test case contains two integer n, m, indicating the number of rabbits and the queries.
　　The following line contains n integers, and the i-th integer Wi indicates the weight of the i-th rabbit.
　　Then m lines follow. Each line represents a query. It contains two integers L and R, meaning the king wanted to ask about the situation that if he sent all rabbits from the L-th one to the R-th one into prison.
　　(1 <= n, m, Wi <= 200000, 1 <= L <= R <= n)
　　The input ends with n = 0 and m = 0.

Output

For every query, output one line indicating the answer.

Sample Input

3 2 2 1 4 1 2 1 3 6 4 3 6 1 2 5 3 1 3 4 6 4 4 2 6 0 0

Sample Output

2 1 1 3 1 2

Hint

In the second case, the answer of the 4-th query is 2, because only 1 and 5 is co-prime with other numbers in the interval [2,6] .

AC

• 詢問與區(qū)間內數(shù)字互質的個數(shù)
• 可以統(tǒng)計每個數(shù)字三個區(qū)間（左邊最近不互質點，i），（i, 右邊最近不互質點），（左邊最近不互質，右邊最近不互質）
• ans = 區(qū)間長度 - 區(qū)間1 - 區(qū)間2 + 區(qū)間3

#include <iostream> #include <stdio.h> #include <map> #include <unordered_map> #include <vector> #include <set> #include <queue> #include <stack> #include <cstring> #include <cmath> #include <iomanip> #include <algorithm> #define N 200005 #define lowbit(x) (x & (-x)) #define mem(a, b) memset(a, b, sizeof(a)) #define REP(i, n) for (int i = 1; i <= (n); ++i) #define rep(i, n) for (int i = 0; i < (n); ++i) typedef long long LL; using namespace std; int n, m, a[N], L[N], R[N], ans[3][N], c[N], len[N]; struct ac{int l, r, id;bool operator <(const ac &t) const{return r < t.r;} }q[N], sum[3][N];void init() {map<int, int> mp;mp.clear();REP(i, n) {L[i] = 0;int t = a[i];for (int j = 2; j * j <= t; ++j) {if (t % j) continue;if(mp.find(j) != mp.end()) L[i] = max(L[i], mp[j]);mp[j] = i;while (t % j == 0) t /= j;}if (t > 1) {if (mp.find(t) != mp.end()) L[i] = max(L[i], mp[t]);mp[t] = i;}}mp.clear();for (int i = n; i >= 1; --i) {int t = a[i];R[i] = n + 1;for (int j = 2; j * j <= t; ++j) {if (t % j) continue;if (mp.find(j) != mp.end()) R[i] = min(R[i], mp[j]);mp[j] = i;while (t % j == 0) t /= j;}if (t > 1) {if (mp.find(t) != mp.end()) R[i] = min(R[i], mp[t]);mp[t] = i;}}REP(i, n) {sum[0][i] = {L[i], i}; // 記錄點左邊不互質區(qū)間sum[1][i] = {i, R[i]}; // 記錄點右邊不互質區(qū)間sum[2][i] = {L[i], R[i]}; // 記錄點左右不互質區(qū)間}// 按照有區(qū)間排序sort (sum[0] + 1, sum[0] + n + 1);sort (sum[1] + 1, sum[1] + n + 1);sort (sum[2] + 1, sum[2] + n + 1); } void update(int x) {if (x == 0) return; // 左邊不存在不互質的點while (x <= n) {c[x] += 1;x += lowbit(x);} }int Sum(int x) {int sum = 0;while (x > 0) {sum += c[x];x -= lowbit(x);}return sum; }void solve() {rep(i, 3) {mem(c, 0); // 清空樹狀數(shù)組int j = 1, k = 1;while (k <= m) {while (j <= n && sum[i][j].r <= q[k].r) {update(sum[i][j].l);++j;}ans[i][q[k].id] = Sum(q[k].r) - Sum(q[k].l - 1);++k;}} } int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin); #endifwhile (scanf("%d %d", &n, &m) != EOF) {if (n + m == 0) break;REP(i, n) scanf("%d", &a[i]);REP(i, m) {scanf("%d %d", &q[i].l, &q[i].r);q[i].id = i;len[i] = q[i].r - q[i].l + 1;}sort(q + 1, q + m + 1);init();solve();REP(i, m) {printf("%d\n", len[i] - ans[0][i] - ans[1][i] + ans[2][i]);}}return 0; }

總結

以上是生活随笔為你收集整理的HDU-4777 Rabbit Kingdomom(树状数组、区间离线)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。