浅念づ昔夜's Blog

Like author, like book.

0%

CF438D The Child and Sequence

发表于 分类于
本文字数： 428 阅读时长 ≈ 2 分钟

传送门

Solution

设 m=n mod pm=n\bmod p，那么一定有 m≤n2m\le \dfrac{n}{2}。因此每个点最多经过 log⁡ai\log a_i 次取余就会变成 11。

线段树维护序列区间最大值与区间和，当二分到某最大值小于模数 xx 的区间，直接返回。否则一直向下至叶节点暴力取余即可。

Code

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
#include <bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
using namespace std;
typedef long long ll;

const ll N = 1e5 + 10;

ll n, m, a[N];
struct Node {
    ll l, r, maxn, sum;
} T[N << 2];

void push_up(ll k)
{
    T[k].maxn = max(T[ls].maxn, T[rs].maxn);
    T[k].sum = T[ls].sum + T[rs].sum;
}

void build(ll k, ll l, ll r)
{
    T[k].l = l; T[k].r = r;
    if (l == r) {
        T[k].maxn = T[k].sum = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(k);
}

void modify(ll k, ll x, ll y, ll z)
{
    if (T[k].maxn < z) return;
    if (T[k].l == T[k].r) {
        T[k].maxn = T[k].sum = (T[k].sum % z);
        return;
    }
    ll mid = (T[k].l + T[k].r) >> 1;
    if (x <= mid) modify(ls, x, y, z);
    if (mid < y) modify(rs, x, y, z);
    push_up(k);
}

void change(ll k, ll x, ll z)
{
    if (T[k].l == T[k].r && T[k].l == x) {
        T[k].maxn = T[k].sum = z;
        return;
    }
    ll mid = (T[k].l + T[k].r) >> 1;
    if (x <= mid) change(ls, x, z);
    if (mid < x) change(rs, x, z);
    push_up(k);
}

ll query(ll k, ll x, ll y)
{
    if (x <= T[k].l && T[k].r <= y) 
        return T[k].sum;
    ll mid = (T[k].l + T[k].r) >> 1, res = 0;
    if (x <= mid) res += query(ls, x, y);
    if (mid < y) res += query(rs, x, y);
    return res;
}

int main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    build(1, 1, n);
    while (m--) {
        ll opt, x, y, z;
        scanf("%lld%lld%lld", &opt, &x, &y);
        if (opt == 1)
            printf("%lld\n", query(1, x, y));
        else if (opt == 2) {
            scanf("%lld", &z);
            modify(1, x, y, z);
        } else
            change(1, x, y);
    }
    return 0;
}