Problem 1007 幸运数 线段树成段更新

题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$。

定义一个数 $k$ 的权值为 $w_k$，其中 $w_k$ 为 $k$ 的因数中 1 的个数。

定义一个区间 $[l,r]$ 的权值为 $\gcd\{a_l,a_{l+1},\cdots,a_r\}$ 的权值。

现在有 $m$ 次操作，每次操作为将区间 $[l,r]$ 内的数加上 $x$（即 $a_l\gets a_l+x,a_{l+1}\gets a_{l+1}+x,\cdots,a_r\gets a_r+x$）。

对于每次操作，求出操作后 $[1,n]$ 中有多少个区间的权值为素数。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

接下来 $m$ 行，每行包含三个整数 $l,r,x$，表示对区间 $[l,r]$ 内的数加上 $x$。

输出格式

对于每次操作，输出操作后 $[1,n]$ 中有多少个区间的权值为素数。

数据范围

$1\le n\le 10^5$，
$1\le m\le 10^5$，
$1\le a_i,x\le 10^6$

输入样例：

5 3
1 2 3 4 5
1 5 1
2 3 2
1 3 1

输出样例：

3
4
3

解题思路

注意到一个数的因数中 1 的个数只与其质因数分解后的指数有关，可以预处理出每个质数的指数数组，即 primes[i] 表示第 $i$ 个质数的指数。

对于每个区间 $[l,r]$，求出其权值的质因数分解，即对于每个质数 $p$，求出区间 $[l,r]$ 内 $p$ 的最小指数 $k$，则该区间的权值为 $\prod_{i=1}^np^{k_i}$ 的权值。

然后我们可以把区间加操作看做将区间内所有数乘上 $x+1$，那么区间内每个质数的指数也都加上了 $1$，因此只需要实现一个支持区间乘的数据结构即可。

考虑使用线段树维护区间乘积，对于每个节点，我们可以维护其子节点的质因数分解的指数数组，然后合并子节点时，将指数数组相应位置相加即可。

对于查询区间权值是否为素数，我们可以使用线性筛判定。

时间复杂度

每次操作的时间复杂度为 $O(\log n + k\log n)$，其中 $k$ 为质因数的个数，因此总时间复杂度为 $O(m\log n + kn\log n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100010, M = 1000000;

int n, m;
int w[M + 10];  // w表示每个数的权值
int primes[N], cnt;  // primes表示前cnt个质数
int id[M + 10];  // id[i]表示i这个数在primes数组中的位置
int st[N << 2][20];  // st表示线段树节点中每个质数的指数
bool is_prime[M + 10];  // is_prime[i]表示i是否为质数
int res;  // res表示答案

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!is_prime[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            is_prime[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

void init()
{
    for (int i = 2; i <= M; i ++ )
        if (!is_prime[i])
        {
            int t = i, cnt = 0;
            while (t <= M) w[t] ++, t *= i, cnt ++ ;
        }
    get_primes(N - 1);
    for (int i = 1; i <= cnt; i ++ ) id[primes[i]] = i;
}

void pushup(int u)
{
    for (int i = 1; i <= cnt; i ++ )
        st[u][i] = st[u << 1][i] + st[u << 1 | 1][i];
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        st[u][id[w[l]]] = 1;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void modify(int u, int l, int r, int ql, int qr, int c)
{
    if (ql <= l && r <= qr)
    {
        for (int i = 1; i <= cnt; i ++ )
            st[u][i] += c * st[u][i];
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) modify(u << 1, l, mid, ql, qr, c);
    if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, c);
    pushup(u);
}

void query(int u, int l, int r, int k)
{
    if (l == r)
    {
        bool is_prime = true;
        for (int i = 2; i <= sqrt(w[l]); i ++ )
            if (w[l] % i == 0)
            {
                is_prime = false;
                break;
            }
        if (w[l] <= 1) is_prime = false;
        if (is_prime) res += st[u][k];
        return;
    }
    int mid = l + r >> 1;
    query(u << 1, l, mid, k), query(u << 1 | 1, mid + 1, r, k);
}

int main()
{
    init();
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m -- )
    {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        modify(1, 1, n, l, r, x);
        res = 0;
        query(1, 1, n, x + 1);
        printf("%d\n", res);
    }
    return 0;
}