7.CF438D The Child and Sequence 线段树维护区间取模

7.CF438D The Child and Sequence 线段树维护区间取模

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定数列，区间查询和，区间取模，单点修改。
记录区间最大值，对于区间最大值小于模数的区间不予更新

洛谷传送门：CF438D The Child and Sequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：D. The Child and Sequence (codeforces.com)

题目分析

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

记录区间最大值，对于区间最大值小于模数的区间不予更新，这样更新不会占用较多的时间。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l, mid
    #define rson rs, mid + 1, r

    int tree[N << 2], maxx[N << 1], lazy[N << 1];

    inline void push_up(int rt){
        tree[rt] = tree[ls] + tree[rs];
        maxx[rt] = std::max(maxx[ls], maxx[rs]);
    }

    void build(int rt, int l, int r){
        if(l == r){
            cin >> tree[rt], maxx[rt] = tree[rt];
            return;
        }
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }

    void update_part(int rt, int l, int r, int L, int R, int mod){
        if(maxx[rt] < mod) return;
        if(l == r){
            tree[rt] %= mod;
            maxx[rt] %= mod;
            return;
        }
        int mid = l + r >> 1;
        if(mid >= L) update_part(lson, L, R, mod);
        if(mid < R) update_part(rson, L, R, mod);
        push_up(rt);
    }

    void update_single(int rt, int l, int r, int pos, int val){
        if(l == r){
            tree[rt] = maxx[rt] = val;
            return;
        }
        int mid = l + r >> 1;
        if(mid >= pos) update_single(lson, pos, val);
        else update_single(rson, pos, val);
        push_up(rt);
    }

    int query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tree[rt];
        int mid = l + r >> 1, ans = 0;
        if(mid >= L) ans += query(lson, L, R);
        if(mid < R) ans += query(rson, L, R);
        return ans;
    }
}

#define SEGRG 1, 1, n

inline void solve(){
    int n, m; cin >> n >> m;
    SegTree::build(SEGRG);
    while(m--){
        int op; cin >> op; 
        if(op == 1){
            int l, r; cin >> l >> r;
            cout << SegTree::query(SEGRG, l, r) << endl;
        } else if(op == 2) {
            int l, r, x; cin >> l >> r >> x;
            SegTree::update_part(SEGRG, l, r, x);
        } else {
            int k, x; cin >> k >> x;
            SegTree::update_single(SEGRG, k, x);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92