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

希望能帮助到大家！