题目链接

这里这里

题解

是一道很水的题。

由于涉及到了区间查询操作(这一看不就是线段树嘛),所以我使用了埃筛+线段树的操作。

在建树前进行一次筛选,得到一张质数表,再根据质数表建树。

void GetList(int m) {
    for (int i = 2; i <= m; i++)
        Prime[i] = true;
    Prime[0] = false;
    Prime[1] = false;
    for (int i = 2; i <= m; i++) {
        if (!Prime[i])
            continue;
        else
            for (int j = i * 2; j <= m; j += i)
                Prime[j] = false;
    }
}

void Build(int& now, int l, int r, int x, int k) {
    if (now == 0)
        now = ++cnt;
    if (l == r) {
        Seg[now].sum = k;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid)
        Build(Seg[now].L, l, mid, x, k);
    else
        Build(Seg[now].R, mid + 1, r, x, k);
    Seg[now].sum = Seg[Seg[now].L].sum + Seg[Seg[now].R].sum;
}


GetList(m);
for (int i = 1; i <= m; i++)
    if (Prime[i] == true)
        Build(root, 1, m, i, 1);//如果是质数,就把该点标记为1
    else
        Build(root, 1, m, i, 0);//如果不是质数,就标记为0

建树时按照上面这么搞,查询的时候就可以和普通的线段树一样维护了。


徒具人形