SP19568 题解

前言

题目传送门！

更好的阅读体验？

好的线段树练习题。

思路

我们要维护三个操作：

1. 单点加。
2. 区间推平。
3. 区间查询质数。

区间推平可以想到珂朵莉树，但是我不会，于是考虑线段树。

容易想到，判断质数部分可以预处理。用欧拉筛，这一点不用多说了吧。

为了叙述方便，用 \(\operatorname{isprime}(x)\) 表示 \(x\) 是否为质数。

然后就是很套路的线段树了，只用维护一个覆盖（\(cov_i\)）的 tag 和总答案（\(sum_i\)）。

区间推平与查询和线段树板子几乎一样。单点修改时，把 \(cov_i\) 加上 \(k\)，\(sum_i = \operatorname{isprime}(cov_i + k)\)。

至于下传，也很简单：\(sum_i = \operatorname{isprime}(k) \times (r - l + 1)\)，\(cov_i = k\)。

然后？就没有然后了。代码非常好打，感觉只有蓝。

完整代码

懒得打注释了，上面都说清楚了吧。

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

希望能帮助到大家！