【离线】牛客小白月赛39 G
2023-12-16 05:10:03
题意
思路
考虑离线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;
}
文章来源:https://blog.csdn.net/weixin_62528401/article/details/135027604
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!