|
|
#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;
|
|
|
}
|
