|
|
// 编译器选择GCC C++14
|
|
|
#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;
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
int a[N];
|
|
|
|
|
|
// 线段树
|
|
|
#define ls (u << 1)
|
|
|
#define rs (u << 1 | 1)
|
|
|
#define mid ((l + r) >> 1)
|
|
|
struct Node {
|
|
|
int l, r, len; // 区间范围
|
|
|
int sum; // 区间和
|
|
|
int tag; // 懒标记
|
|
|
} tr[N << 2];
|
|
|
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[ls].sum + tr[rs].sum;
|
|
|
}
|
|
|
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u].l = l, tr[u].r = r, tr[u].len = r - l + 1;
|
|
|
tr[u].tag = -1; // 多组测试数据，需要清零
|
|
|
if (l == r) {
|
|
|
tr[u].sum = !st[a[l]]; // 如果a[l]是质数，那么!st[a[l]]==1,则单节点的tr[u].sum=1.否则为0
|
|
|
return;
|
|
|
}
|
|
|
build(ls, l, mid), build(rs, mid + 1, r);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
// 修改u节点的懒标记和统计信息
|
|
|
void update(int u, int v) {
|
|
|
tr[u].tag = v;
|
|
|
if (tr[u].tag == 1) tr[u].sum = tr[u].len;
|
|
|
if (tr[u].tag == 0) tr[u].sum = 0;
|
|
|
}
|
|
|
|
|
|
void pushdown(int u) {
|
|
|
if (~tr[u].tag) {
|
|
|
// 向左儿子传递
|
|
|
update(ls, tr[u].tag);
|
|
|
// 向左儿子传递
|
|
|
update(rs, tr[u].tag);
|
|
|
// 终于完成向左右儿子传递懒标记的任务，将自己的懒标记清除
|
|
|
tr[u].tag = -1;
|
|
|
}
|
|
|
}
|
|
|
|
|
|
void modify(int u, int L, int R, int v) {
|
|
|
if (tr[u].tag == v) return; // 剪枝
|
|
|
int l = tr[u].l, r = tr[u].r;
|
|
|
if (l > R || r < L) return;
|
|
|
if (l >= L && r <= R) {
|
|
|
if (v == 0) {
|
|
|
tr[u].sum = 0;
|
|
|
tr[u].tag = 0;
|
|
|
return;
|
|
|
}
|
|
|
if (v == 1) {
|
|
|
tr[u].sum = tr[u].len;
|
|
|
tr[u].tag = 1;
|
|
|
return;
|
|
|
}
|
|
|
}
|
|
|
pushdown(u);
|
|
|
modify(ls, L, R, v), modify(rs, L, R, v);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
int query(int u, int L, int R) {
|
|
|
int l = tr[u].l, r = tr[u].r;
|
|
|
if (l > R || r < L) return 0;
|
|
|
if (tr[u].sum == 0) return 0; // 剪枝，优化
|
|
|
if (l >= L && r <= R) return tr[u].sum;
|
|
|
|
|
|
pushdown(u);
|
|
|
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 = 0;
|
|
|
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;
|
|
|
} |
