\(CNTPRIME\) - \(Counting\) \(Primes\)
题目描述
给定初始序列 \(A\)，然后对原序列有以下操作：
- 操作 \(1\)：
0 l r v将区间\([l,r]\) 全赋值为\(v\)。 - 操作 \(2\)：
1 l r查询区间\([l,r]\) 的质数个数。
注意：多组测试和特殊的输出。
题目分析：
就是一道板子题，首先我们先用欧拉筛筛出值域 \([2,10^6]\)内的素数并开桶打标记（实际上一个欧拉筛就行了）。
此时，线段树维护的是当前区间内质数的个数，我们可以将操作 \(1\) 变成如下操作：
- 若 \(v\) 属于质数，则将区间 \([l,r]\) 内的数全赋值成 \(1\)。
- 若 \(v\) 不属于质数，则将区间 \([l,r]\) 内的数全赋值成 \(0\)。
那么，操作 \(2\) 此时显然就变成了一个区间求和。
时间复杂度，\(O(nlgn)\)。
线段树解法
// 编译器选择GCC C++14
#include <bits/stdc++.h>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
// 欧拉筛
const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] * i <= n; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int a[N];
// 线段树
struct Node {
int l, r; // 区间范围
int sum; // 区间和
int tag; // 懒标记
} tr[N << 2];
void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
tr[u].tag = 0; // 多组测试数据，需要清零
if (l == r) {
tr[u].sum = !st[a[l]]; // 如果a[l]是质数，那么!st[a[l]]==1,则单节点的tr[u].sum=1.否则为0
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
// 修改u节点的懒标记和统计信息
void update(int u, int tag) {
tr[u].tag = tag;
if (tr[u].tag == 1) tr[u].sum = tr[u].r - tr[u].l + 1;
if (tr[u].tag == 2) tr[u].sum = 0;
}
void pushdown(int u) {
// 向左儿子传递
update(ls, tr[u].tag);
// 向左儿子传递
update(rs, tr[u].tag);
// 终于完成向左右儿子传递懒标记的任务，将自己的懒标记清除
tr[u].tag = 0;
}
void modify(int u, int l, int r, int tag) {
if (tr[u].tag == tag) return; // 剪枝
if (l <= tr[u].l && r >= tr[u].r) {
if (tag == 1) {
tr[u].sum = tr[u].r - tr[u].l + 1;
tr[u].tag = 1;
return;
}
if (tag == 2) {
tr[u].sum = 0;
tr[u].tag = tag;
return;
}
}
if (tr[u].tag) pushdown(u);
if (tr[ls].r >= l) modify(ls, l, r, tag);
if (tr[rs].l <= r) modify(rs, l, r, tag);
pushup(u);
}
int query(int u, int l, int r) {
if (tr[u].sum == 0) return 0; // 剪枝，优化
if (l <= tr[u].l && r >= tr[u].r) return tr[u].sum;
if (tr[u].tag) pushdown(u);
if (tr[rs].l > r) return query(ls, l, r);
if (tr[ls].r < l) return query(rs, l, r);
return query(ls, l, r) + query(rs, l, r);
}
/*
Case 1:
1
4
*/
int main() {
#ifndef ONLINE_JUDGE
freopen("SP13015.in", "r", stdin);
#endif
// 加快读入
ios::sync_with_stdio(false), cin.tie(0);
// 欧拉筛，筛出1e6以内所有的质数
get_primes(1e6);
int T;
cin >> T;
for (int x = 1; x <= T; x++) {
cout << "Case " << x << ':' << endl;
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
// 构建线段树
build(1, 1, n);
while (q--) {
int op;
cin >> op;
if (op == 0) { // 全赋值为v
int l, r, v;
cin >> l >> r >> v;
int tag;
if (!st[v])
tag = 1;
else
tag = 2;
modify(1, l, r, tag); // 如果v是质数，那么整个区间都设置为1.否则，全部设置为0
}
if (op == 1) { // 查询质数个数
int l, r;
cin >> l >> r;
cout << query(1, l, r) << endl;
}
}
}
return 0;
}
柯朵莉树解法
#include <bits/stdc++.h>
using namespace std;
// 欧拉筛
const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] * i <= n; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
// 柯朵莉树模板
struct Node {
int l, r; // l和r表示这一段的起点和终点
mutable int v; // v表示这一段上所有元素相同的值是多少,注意关键字 mutable,使得set中结构体属性可修改
bool operator<(const Node &b) const {
return l < b.l; // 规定按照每段的左端点排序
}
};
set<Node> s; // 柯朵莉树的区间集合
// 分裂:[l,x-1],[x,r]
set<Node>::iterator split(int x) {
auto it = s.lower_bound({x});
if (it != s.end() && it->l == x) return it; // 一击命中
it--; // 没有找到就减1个继续找
if (it->r < x) return s.end(); // 真的没找到,返回s.end()
int l = it->l, r = it->r, v = it->v; // 没有被返回，说明找到了,记录下来，防止后面删除时被破坏
s.erase(it); // 删除整个区间
s.insert({l, x - 1, v}); //[l,x-1]拆分
// insert函数返回pair，其中的first是新插入结点的迭代器
return s.insert({x, r, v}).first; //[x,r]拆分
}
// 区间加
void add(int l, int r, int v) {
// 必须先计算itr,后计算itl
auto R = split(r + 1), L = split(l);
for (auto it = L; it != R; it++) it->v += v;
}
// 区间赋值
void assign(int l, int r, int v) {
auto R = split(r + 1), L = split(l);
s.erase(L, R); // 删除旧区间
s.insert({l, r, v}); // 增加新区间
}
int query(int l, int r) {
int res = 0;
auto R = split(r + 1), L = split(l);
for (auto it = L; it != R; it++) {
if (!st[it->v]) res += it->r - it->l + 1;
}
return res;
}
int t, n, q;
/*
Case 1:
1
4
*/
int main() {
#ifndef ONLINE_JUDGE
freopen("SP13015.in", "r", stdin);
#endif
ios::sync_with_stdio(false), cin.tie(0);
get_primes(1e6);
cin >> t;
for (int i = 1; i <= t; i++) {
cout << "Case " << i << ':' << endl;
cin >> n >> q;
s.clear();
for (int j = 1, x; j <= n; j++)
cin >> x, s.insert({j, j, x});
for (int j = 1, op, x, y, v; j <= q; j++) {
cin >> op >> x >> y;
if (!op) {
cin >> v;
assign(x, y, v);
} else {
cout << query(x, y) << endl;
}
}
}
return 0;
}