我没有打这个比赛，但是队友让我做了这个题（确实是好题），这次做的这个题目让我的线段树的理解获得了极大的提升，以往我的思维想的是：
pushup维护递归到子树后子树传递给父亲的信息。
pushdown维护父亲将要对子树的影响的信息。
回到这个题目：
通过分析题意结合唯一分解定理易知：
1.如果x==0 修改后的A[i]=ai,等于本身，即修改后原先是质数，那么修改后仍然是质数，原先不是质数，修改后仍不是质数。
2.如果x>1, 修改后的A[i]=p*ai(p>=1)。
1.如果p>1 那么ai修改后一定为合数。
2.如果p=1，那么ai修改后不变，他仍然是之前的数（不是质数或是质数）。
3 如果x=1,修改后的A[i]=i*ai，如果ai不为1，那么一定变合数；如果ai为1，A[i]变合数还是质数和i有关，i为质数即A[i]为质数，反之合数。
在此，所有的情况就分析完了，接下来分析怎么样实现代码和改使用什么数据结构维护这些查询
暴力模拟，暴力啊！暴力出奇迹,看到 n m是1e5的级别这时候如果想暴力就没有写下去的必要了！
这时候问自己，什么能够维护区间？什么能在 mongn时间复杂度时间内优雅跑出答案？，答案呼之欲出！！！线段树！
再想想实现方法：
1.我们要的不是这个a[i]这个数的值，这个数只用一个用，他是否为质数，或者不是，我们要的是质数的总和，那么是质数标记1就行了，不是质数标记成0？，还不够！
2.本题有某个点质数和合数一直不变的情况，即a[1]的情况，a[i]无论x为什么a[i]都不会变，因为i==1；本题有非质数转化为合数的情况，如上文所提，i!=1&&a[i]==1时，a[i]变成质数和合数取决于i的是质数还是合数，而且他变了这一次后，便失去的这个特殊性
3.所以我们还要想办法将非质数转变成质数，这个==懒标记lz用的十分精髓，而且我从来没做过子树向父亲传递懒标记的题目，这个题目的懒标记用的十分6：
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; struct node { int l; int r; int sum;// 1 质数 0 合数 int lz; //1 质数 0 合数 2 是非质数（为1）但是可能变质数 } tr[N << 2]; int l, r, x, op; int n, m; bool f[N * 3]; int a[N]; void init() {//埃式筛 f[1] = true; for (int i = 2; i <= 5e5 + 10; i++) { for (int j = i * 2; j <= 5e5 + 10; j += i) { f[j] = true; } } } void pushup(int u) {//向父亲传递影响 if (tr[u << 1].lz == 0 && tr[u << 1 | 1].lz == 0) tr[u].lz = 0;//如果左区间和右区间都为合数，这个父亲区间再也不会有质数了，打一个标签 else tr[u].lz = 2;//这个区间可能有1变成质数的情况，要向下递归看 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; if (l == r) { //Tr[u].lz=is[a[l]]; if (a[l] == 1 && l != 1) tr[u].lz = 2;//如果a[i]=1,而且i!=1，那么它保留了变成质数的可能 else if (!f[a[l]]) tr[u].lz = 1; //如果为质数 标记1 else tr[u].lz = 0;//合数标记 0 if (tr[u].lz == 1) tr[u].sum = 1; //0现在是质数 1不是质数. else tr[u].sum = 0; return; } int mid = l + r >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u); } void update(int u, int l, int r, int k) { if (tr[u].lz == 0) return;//如果这个区间没有质数了，直接返回 if (tr[u].l >= l && tr[u].r <= r) { if (tr[u].l == tr[u].r) { if (k > 1) { //所有质数变合数，合数还是合数，除a[1]的情况 if (tr[u].l == 1 && tr[u].lz == 1) { a[1]是质数，那么它永远为质数，是合数则永远为合数 tr[u].sum = 1; tr[u].lz = 1; } else {//其他质数全变合数 tr[u].sum = 0; tr[u].lz = 0; } } else { // 质变和 为一的数可能会变质数 if (a[tr[u].l] == 1 || tr[u].l == 1) { //a[i]=1的情况，可能变质数 a[tr[u].l] *= tr[u].l; if (!f[a[tr[u].l]]) tr[u].sum = 1, tr[u].lz = 1; else tr[u].sum = 0, tr[u].lz = 0; } else { //其他质数全变合数 if (tr[u].lz == 1) tr[u].sum = 0, tr[u].lz = 0; } } } return; } int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) update(u << 1, l, r, k); if (r > mid) update(u << 1 | 1, l, r, k); pushup(u); } int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { return tr[u].sum; } int mid = tr[u].l + tr[u].r >> 1; int s = 0; if (l <= mid) s += query(u << 1, l, r); if (r > mid) s += query(u << 1 | 1, l, r); return s; } int main() { init(); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); build(1, 1, n); while (m--) { scanf("%d", &op); if (op == 1) { scanf("%d%d%d", &l, &r, &x); if (x != 0) update(1, l, r, x);//x=0,更新等于没有更新 cout << query(1, l, r) << "\n"; } else { scanf("%d%d", &l, &r); cout << query(1, l, r) << "\n"; } } }
完结撒花
