【离线】牛客小白月赛39 G

登录—专业IT笔试面试备考平台_牛客网

题意

思路

考虑离线Bit做法

这种离线Bit，一般都是去考虑二维数点就能写清楚了

确定好两维：x 轴是1 ~ n， y 轴是 k 的大小

然后去遍历值域，如果值域很大的话需要排序+离散化，但是这里不需要

这里有个容易想错的点，对于 Bit 维护的 y 轴，query(x)维护的是 y 轴上 <= x 的值，也就是说，query是个 y 轴上的前缀和

query(x)是个前缀和，它不是 y轴 上某个数的值

这样就直接写就好了，注意询问需要用 vector 存，否则会出错

#include <bits/stdc++.h>

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

constexpr int N = 3e6 + 10;
constexpr int M = 1e4 + 10;
constexpr int mod = 998244353;
constexpr int Inf = 0x3f3f3f3f;

std::vector<std::pair<int, int> > V[N];

int len = 0;
int prime[N], vis[N], minp[N];
int n[N], k[N];
int id[N];
int ans[N];
int tr[N];

void P_init(int n) {
	for (int i = 2; i <= n; i ++) {
		if (!vis[i]) {
			minp[i] = i;
			prime[++len] = i;
		}
		for (int j = 1; i <= n / prime[j]; j ++) {
			vis[i * prime[j]] = 1;
			minp[i * prime[j]] = prime[j];
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
}
void add(int x, int k) {
	for (int i = x; i <= 3e6; i += lowbit(i)) {
		tr[i] += k;
	}
}
int query(int x) {
	int res = 0;
	for (int i = x; i; i -= lowbit(i)) {
		res += tr[i];
	}
	return res;
}
void solve() {
	int q;
	std::cin >> q;
	for (int i = 1; i <= q; i ++) {
		int n, k;
		std::cin >> n >> k;
		V[n].push_back({k, i});
	}
	for (int i = 1; i <= 3e6; i ++) {
		if (i != 1) add(minp[i], 1);
		for (auto [k, id] : V[i]) {
			ans[id] = query(3e6) - query(k - 1);
		}
	}
	for (int i = 1; i <= q; i ++) {
		std::cout << ans[i] << "\n";
	}
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = 1;
	P_init(3e6);
    while(t --) {
        solve();
    }
    return 0;
}