[CF438D] The Child and Sequence

[CF438D] The Child and Sequence - 线段树

Description

给定数列，查询区间和，区间取模，单点修改。

Solution

线段树，记录区间最大值，如果大于要取模的数就把修改暴力递归下去。

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

struct SegmentTree
{
    struct Node
    {
        int sum;
        int mx;

        Node operator+(const Node &rhs)
        {
            return {sum + rhs.sum, max(mx, rhs.mx)};
        }
    };

    vector<Node> node;
    int n;

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

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

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

    void single_modify(int p, int l, int r, int pos, int key)
    {
        if (l == r)
            node[p] = {key, key};
        else if (pos <= (l + r) / 2)
            single_modify(p * 2, l, (l + r) / 2, pos, key), node[p] = node[p * 2] + node[p * 2 + 1];
        else
            single_modify(p * 2 + 1, (l + r) / 2 + 1, r, pos, key), node[p] = node[p * 2] + node[p * 2 + 1];
    }

    void SingleModify(int pos, int key)
    {
        single_modify(1, 1, n, pos, key);
    }

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

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

    Node query(int p, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql)
            return {0, 0};
        if (l >= ql && r <= qr)
            return node[p];
        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).sum;
    }
};

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

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

    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, t4;
        cin >> t1 >> t2 >> t3;
        if (t1 == 1)
        {
            cout << seg.Query(t2, t3) << endl;
        }
        else if (t1 == 2)
        {
            cin >> t4;
            seg.Modify(t2, t3, t4);
        }
        else if (t1 == 3)
        {
            seg.SingleModify(t2, t3);
        }
    }
}