SP19568 PRMQUER - Prime queries 题解

题目链接：SP19568 PRMQUER - Prime queries

题意：

这是一个简单的题目

给定 $N$ 个数，你需要对它们依次进行 $Q$ 次操作。每次操作的格式如下。

三个整数 $A$ $V$ $l$ 表示给第 $l$ 个数加上 $V$ 。

四个整数 $R$ $a$ $l$ $r$ 表示把区间 $[l,r]$ 的数都变为 $a$ 。

三个整数 $Q$ $l$ $r$ 表示询问区间 $[l,r]$ 里，小于等于 $10^7$ 的素数有多少个。

数据保证任何时刻这 $N$ 个数都不会有一个数大于 $10^9$ 。

输入格式：

第一行两个整数 $N$ 和 $Q$ 分别表示数的个数和操作的个数，第二行有 $N$ 个整数，表示这些数的初始大小。之后 $Q$ 行每行一次操作，输入格式如题目描述所述。

输出格式：

对于每个操作 $3$ 输出一行整数表示这个操作的答案。

数据范围：

$1\leq N\leq10^5,~1\leq Q\leq10^5,~V\leq10^3,~a_i \leq10^8,~a \leq10^7,~1\leq l\leq r \leq N$ 。

只需要把 $10^7$ 以内的素数筛一遍，然后维护线段树就可以了。

具体地，我们维护 $\mathrm{val}$ 和 $\mathrm{sum}$ 分别表示区间覆盖的值和答案，

那么单点修改就是 $\mathrm{val} \gets \mathrm{val} + k, ~\mathrm{sum} \gets [(\mathrm{val} + k) \in \mathbb{P}]$ ，

区间推平就是 $\mathrm{val} \gets k, ~\mathrm{sum} \gets[k \in\mathbb{P}] \times (r - l + 1)$ ，其中 $[x \in \mathbb{P}]$ 表示 $x$ 属于 $10^7$ 以内的质数。

时间复杂度 $\mathcal{O}(10^7 + Q\log N)$

代码：（直接搬的题解）

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 4e5 + 5, MX = 1e7;
bool flag[MX + 5];
int prime[MX + 5], cur;
void euler() //欧拉筛 
{
	flag[0] = flag[1] = true;
	for (int i = 2; i <= MX; i++)
	{
		if (!flag[i]) prime[++cur] = i;
		for (int j = 1; j <= cur; j++)
		{
			if (i * prime[j] > MX) break;
			flag[i * prime[j]] = true;
			if (i % prime[j] == 0) break;
		}
	}
}
bool isp(int x) {return x <= MX && !flag[x];}
struct SegmentTree
{
	int sum[N], cov[N];
	inline int ls(int x) {return x << 1;}
	inline int rs(int x) {return x << 1 | 1;}
	void pushup(int pos) {sum[pos] = sum[ls(pos)] + sum[rs(pos)];}
	void build(int l, int r, int pos)
	{
		if (l == r)
		{
			cin >> cov[pos];
			sum[pos] = isp(cov[pos]);
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, ls(pos)), build(mid + 1, r, rs(pos));
		pushup(pos);
	}
	void lazy(int l, int r, int pos, int k)
	{
		sum[pos] = isp(k) * (r - l + 1);
		cov[pos] = k;
	}
	void pushdown(int l, int r, int pos)
	{
		if (!cov[pos]) return;
		int mid = (l + r) >> 1;
		lazy(l, mid, ls(pos), cov[pos]);
		lazy(mid + 1, r, rs(pos), cov[pos]);
		cov[pos] = 0;
	}
	void update(int l, int r, int pos, int id, int k) //单点加 
	{
		if (l == r)
		{
			cov[pos] += k, sum[pos] = isp(cov[pos]);
			return;
		}
		pushdown(l, r, pos);
		int mid = (l + r) >> 1;
		if (id <= mid) update(l, mid, ls(pos), id, k);
		else update(mid + 1, r, rs(pos), id, k);
		pushup(pos);
	}
	void modify(int l, int r, int pos, int L, int R, int k) //区间推平 
	{
		if (L <= l && r <= R) return lazy(l, r, pos, k);
		pushdown(l, r, pos);
		int mid = (l + r) >> 1;
		if (L <= mid) modify(l, mid, ls(pos), L, R, k);
		if (mid < R) modify(mid + 1, r, rs(pos), L, R, k);
		pushup(pos);
	}
	int query(int l, int r, int pos, int L, int R)
	{
		if (L <= l && r <= R) return sum[pos];
		pushdown(l, r, pos);
		int mid = (l + r) >> 1, ans = 0;
		if (L <= mid) ans += query(l, mid, ls(pos), L, R);
		if (mid < R) ans += query(mid + 1, r, rs(pos), L, R);
		return ans;
	}
} seg;
int main()
{
	ios::sync_with_stdio(false);
	euler();
	int n, T;
	cin >> n >> T;
	seg.build(1, n, 1);
	while (T--)
	{
		char c;
		cin >> c;
		if (c == 'A')
		{
			int k, id;
			cin >> k >> id;
			seg.update(1, n, 1, id, k);
		}
		else if (c == 'R')
		{
			int k, l, r;
			cin >> k >> l >> r;
			seg.modify(1, n, 1, l, r, k);
		}
		else if (c == 'Q')
		{
			int l, r;
			cin >> l >> r;
			cout << seg.query(1, n, 1, l, r) << '\n';
		}
	}
	return 0;
}