题意:单点修改,区间取模,区间和。

线段树。
由于取模不满足结合律所以转化为单点取模。
增加维护区间最大值,若区间最大值小于模数则直接略过。
注意到取模次数最多为log次,下证。
若 $ b < \frac{a}{2} $ ,则 $ a \mathbb{mod} b < b < \frac{a}{2} $;
若 $ b \ge \frac{a}{2} $ ,则 $ a \mathbb{mod} b = a - b < \frac{a}{2} $。
所以数 $ a $ 最多取模 $ O(\lg a) $ 次,然而这是一个极不紧的上界。实际上平均情况远优于此(说不定是我口胡的?)。

码(421ms, 700K)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}
const int maxn = 1e5 + 100;
struct Info
{
    long long _max, sum;
    Info(long long a = 0, long long b = 0) : _max(a), sum(b) {}
    Info operator+(const Info& rhs)
    {
        return Info(max(_max, rhs._max), sum + rhs.sum);
    }
} I[maxn * 4];
long long a[maxn] = {0};
int n, m;
void build(int o = 1, int L = 1, int R = n)
{
    if(L == R)
        I[o] = Info(a[L], a[L]);
    else
    {
        int M = (L + R) >> 1;
        build(o << 1, L, M);
        build(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
long long ql, qr, q;
void query(int o = 1, int L = 1, int R = n)
{
    if(ql <= L && R <= qr)
        q += I[o].sum;
    else
    {
        int M = (L + R) >> 1;
        if(ql <= M) query(o << 1, L, M);
        if(M < qr) query(o << 1 | 1, M + 1, R);
    }
}
void modulo(int o = 1, int L = 1, int R = n)
{
    if(L == R)
        I[o] = Info(I[o].sum % q, I[o].sum % q);
    else
    {
        int M = (L + R) >> 1;
        if(ql <= M && I[o << 1]._max >= q) modulo(o << 1, L, M);
        if(M < qr && I[o << 1 | 1]._max >= q) modulo(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
void set(int o = 1, int L = 1, int R = n)
{
    if(L == ql && ql == R)
        I[o] = Info(q, q);
    else
    {
        int M = (L + R) >> 1;
        if(ql <= M) set(o << 1, L, M);
        else set(o << 1 | 1, M + 1, R);
        I[o] = I[o << 1] + I[o << 1 | 1];
    }
}
int main()
{
    read(n, m);
    for(int i = 1; i <= n; i++)
        read(a[i]);
    build();
    while(m--)
    {
        int type; read(type);
        if(type == 1)
        {
            read(ql, qr); q = 0;
            query();
            printf("%I64d\n", q);
        }
        else if(type == 2)
        {
            read(ql, qr, q);
            modulo();
        }
        else
        {
            read(ql, q);
            set();
        }
    }
    return 0;
}

标签: segment tree

添加新评论