[CF920F] SUM and REPLACE

[CF920F] SUM and REPLACE - 线段树

Description

给定 (n) 个数的数组 (a)，(m) 次操作。操作有两种：将 (iin[l,r]) 中的所有 (a_i (le 10^6)) 替换为 (d(a_i))，其中 (d(x)) 表示 (x) 的正约数的个数；求 (displaystylesum_{i=l}^r a_i)

Solution

基础均摊线段树练习题

记录区间和以及区间最大值，如果最大值 (le 2) 就不再递归，否则暴力递归到叶子进行修改

#include <bits/stdc++.h>
using namespace std;

#define int long long

int d[1000005];

struct SegmentTree
{
    int n;

    struct Node
    {
        int mx;
        int sum;
        Node &operator=(int rhs)
        {
            mx = sum = rhs;
            return *this;
        }
        Node operator+(const Node &rhs) const
        {
            return {max(mx, rhs.mx), sum + rhs.sum};
        }
    };
    vector<Node> a;

    SegmentTree(int n) : n(n)
    {
        a.resize(4 * n + 4);
    }

    void build(int p, int l, int r, vector<int> &src)
    {
        if (l == r)
        {
            a[p] = src[l];
        }
        else
        {
            build(p * 2, l, (l + r) / 2, src);
            build(p * 2 + 1, (l + r) / 2 + 1, r, src);
            a[p] = a[p * 2] + a[p * 2 + 1];
        }
    }

    void Build(vector<int> &src)
    {
        build(1, 1, n, src);
    }

    void modify(int p, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
            return;
        if (a[p].mx <= 2)
            return;
        if (l == r)
        {
            a[p] = d[a[p].mx];
        }
        else
        {
            modify(p * 2, l, (l + r) / 2, ql, qr);
            modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
            a[p] = a[p * 2] + a[p * 2 + 1];
        }
    }

    void Modify(int ql, int qr)
    {
        modify(1, 1, n, ql, qr);
    }

    int query(int p, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
            return 0;
        if (l >= ql && r <= qr)
            return a[p].sum;
        return query(p * 2, l, (l + r) / 2, ql, qr) + query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
    }

    int Query(int ql, int qr)
    {
        return query(1, 1, n, ql, qr);
    }
};

signed main()
{
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= 1e6; i++)
    {
        for (int j = i; j <= 1e6; j += i)
        {
            d[j]++;
        }
    }

    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    SegmentTree seg(n);
    seg.Build(a);

    for (int i = 1; i <= m; i++)
    {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        if (t1 == 1)
        {
            // MODIFY
            seg.Modify(t2, t3);
        }
        else
        {
            // QUERY
            cout << seg.Query(t2, t3) << endl;
        }
    }
}