题解 | 质数统计

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pp pop_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define UNIQUE(v) sort(all(v)); v.erase(unique(all(v)), v.end())
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define PQ priority_queue
constexpr ll inf = 1e9 + 7;

template <typename T>
class TreeArray {
private:
	int n;
	vector<T> bit1, bit2;

	void add(vector<T>& bit, int idx, T val) {
		while (idx <= n) {
			bit[idx] += val;
			idx += idx & -idx;
		}
	}

	T sum(const vector<T>& bit, int idx) const {
		T s = 0;
		while (idx > 0) {
			s += bit[idx];
			idx -= idx & -idx;
		}
		return s;
	}

	T prefix(int idx) const {
		return sum(bit1, idx) * idx - sum(bit2, idx);
	}

public:
	TreeArray(int len) : n(len) {
		bit1.assign(n + 1, 0);
		bit2.assign(n + 1, 0);
	}

	void rangeUpdate(int l, int r, T val) {
		add(bit1, l, val);
		add(bit1, r + 1, -val);
		add(bit2, l, val * (l - 1));
		add(bit2, r + 1, -val * r);
	}

	T rangeQuery(int l, int r) const {
		return prefix(r) - prefix(l - 1);
	}

	T pointQuery(int idx) const {
		return rangeQuery(idx, idx);
	}
};

void solve() {
	int n = 1e6 + 10;
	TreeArray<int> tr(n + 1);
	vector<bool> primes(n + 1, true);
	for (int i = 2; i <= n; i++) {
		if (primes[i]) {
			for (int j = 2; j * i <= n; j++) {
				primes[i * j] = false;
			}
		}
	}	

	for (int i = 2; i <= n; i++) {
		if (primes[i] == true) {
			tr.rangeUpdate(i, i, 1);
		}
	}

	int T;
	cin >> T;

	for (int i = 1; i <= T; i++) {
		int l, r;
		cin >> l >> r;
		int ans = tr.rangeQuery(l, r);
		cout << ans << "\n";
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while (t--) solve();
	return 0;
}