CF438D The Child and Sequence

传送门

Solution

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

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

Code

#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;
}