HDU 4777 Rabbit Kingdom

题目链接

题意：给定一些序列，每次询问一个区间，求出这个区间和其他数字都互质的数的个数

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
typedef long long ll;
const ll N = 200005;
int n, m, vis[N], prime[N], pn = 0;

void getprime() {
	for (ll i = 2; i < N; i++) {
		if (vis[i]) continue;
		prime[pn++] = i;
		for (ll j = i * i; j < N; j += i)
			vis[j] = 1;
	}
}

vector<int> g[N];

void getfac(int i) {
	g[i].clear();
	int tmp;
	scanf("%d", &tmp);
	for (int j = 0; j < pn && prime[j] * prime[j] <= tmp; j++) {
		if (tmp % prime[j] == 0) {
			g[i].push_back(prime[j]);
			while (tmp % prime[j] == 0) tmp /= prime[j];
		}
	}
	if (tmp != 1) g[i].push_back(tmp);
}

int v[N], L[N], R[N], ans[N], bit[N];

struct Query {
	int l, r, id;
} q[N];

bool cmp(Query a, Query b) {
	return a.r < b.r;
}

#define lowbit(x) (x&(-x))

void add(int x, int v) {
	if (x == 0) return;
	while (x < N) {
		bit[x] += v;
		x += lowbit(x);
	}
}

int get(int x) {
	int ans = 0;
	while (x) {
		ans += bit[x];
		x -= lowbit(x);
	}
	return ans;
}

int get(int l, int r) {
	return get(r) - get(l - 1);
}

vector<int> sv[N];

int main() {
	getprime();
	while (~scanf("%d%d", &n, &m) && n) {
		memset(v, 0, sizeof(v));
		for (int i = 1; i <= n; i++) {
			getfac(i);
			int left = 0;
			for (int j = 0; j < g[i].size(); j++) {
				left = max(left, v[g[i][j]]);
				v[g[i][j]] = i;
			}
			L[i] = left;
		}
		memset(v, INF, sizeof(v));
		for (int i = n; i >= 1; i--) {
			int right = n + 1;
			for (int j = 0; j < g[i].size(); j++) {
				right = min(right, v[g[i][j]]);
				v[g[i][j]] = i;
			}
			R[i] = right;
		}
		for (int i = 0; i < m; i++) {
			scanf("%d%d", &q[i].l, &q[i].r);
			q[i].id = i;
		}
		for (int i = 1; i <= n; i++) sv[i].clear();
		for (int i = 1; i <= n; i++) sv[R[i]].push_back(i);
		sort(q, q + m, cmp);
		memset(bit, 0, sizeof(bit));
		int u = 1;
		for (int i = 0; i < m; i++) {
			while (u <= n && u <= q[i].r) {
				add(L[u], 1);
				for (int j = 0; j < sv[u].size(); j++) {
					int pv = sv[u][j];
					add(L[pv], -1);
					add(pv, 1);
				}
				u++;
			}
			ans[q[i].id] = q[i].r - q[i].l + 1 - get(q[i].l, q[i].r);
		}
		for (int i = 0; i < m; i++)
			printf("%d\n", ans[i]);
	}
	return 0;
}

思路：现处理出每个位置的Li，Ri表示最多向左向右能有多少是保持都互质的，然后把询问按右区间排序，从左往右每次加入该位置的左端点Li，每次询问就询问满足Li，Ri都包含在这个区间内，所以询问Li到Ri的个数代表不满足的个数，然后每次到一个端点，如果有之前位置的Ri是这个位置，那么就把那个位置的Li减掉，并且标记掉这个点已经不可能符合标记为1

代码：

HDU 4777 Rabbit Kingdom（树状数组）