UESTC 1597 An easy problem C 线段树+延迟操作+一次函数

An easy problem C 线段树+延迟操作+一次函数

Source

2017 UESTC Training for Data Structures

UESTC 1597 An easy problem C

My Solution

题意：N个数排成一列，有三种操作。1.给一段区间内的每个数乘上一个非负整数。
2.给一段区间内的每个数加上一个非负整数.3.询问一段区间的和模上P的值。

线段树+延迟操作+一次函数
用2个lazy数组，分别为lazya[i], lazyb[i]，
表示 lazya[i] * x + lazyb[i]，
即用一个一次函数，或者说一次系数和常数项 来表示每个节点lazy数组的情况。
每次pushdown的时候，如果lazya或者lazyb有至少其中一个值需要向下传递，
则都一起操作。
先把 lazya的值传递给子节点的lazya和lazyb，然后把lazyb的值传递给子节点的lazyb。
且把lazyb传递给子节点的sum的时候，要 sum[son] = mod(sum[son] + (区间长度)*lazyb)。
然后pushup的时候维护sum%p即可。
2个注意点，一、每次+ or * 都要先取模，二、要用long long
复杂度 O(nlogn)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const LL MAXN = 1e5 + 8;

LL sum[4*MAXN], lazya[4*MAXN], lazyb[4*MAXN];
LL findans, MOD;
LL sz;
inline LL mod(LL x)
{
    return x - x / MOD * MOD;
}
inline void init()
{
    memset(sum, 0, sizeof sum);
    memset(lazyb, 0, sizeof lazyb);
    for(LL i = 0; i < 4*MAXN; i++) lazya[i] = 1; } inline void pushdown(LL l, LL r, LL Ind) { LL mid = (l + r) >> 1;
    sum[Ind<<1] = mod(sum[Ind<<1] * lazya[Ind]);
    sum[Ind<<1] = mod(sum[Ind<<1] + mod((mid - l + 1)*lazyb[Ind]));
    sum[(Ind<<1) + 1] = mod(sum[(Ind<<1) + 1] * lazya[Ind]);
    sum[(Ind<<1) + 1] = mod(sum[(Ind<<1) + 1] + mod((r - (mid+1) + 1)*lazyb[Ind]));
    lazya[Ind<<1] = mod(lazya[Ind<<1]*lazya[Ind]);
    lazya[(Ind<<1) + 1] = mod(lazya[(Ind<<1) + 1]*lazya[Ind]);
    lazyb[Ind<<1] = mod(lazyb[Ind<<1]*lazya[Ind]);
    lazyb[(Ind<<1) + 1] = mod(lazyb[(Ind<<1) + 1]*lazya[Ind]);
    lazya[Ind] = 1;
    lazyb[Ind<<1] = mod(lazyb[Ind<<1] + lazyb[Ind]); lazyb[(Ind<<1) + 1] = mod(lazyb[(Ind<<1) + 1] + lazyb[Ind]);
    lazyb[Ind] = 0;
}
inline void pushup(LL Ind)
{
    sum[Ind] = mod(sum[Ind<<1] + sum[(Ind<<1) + 1]);
}
inline void _Query(LL a, LL b, LL l, LL r, LL Ind){
    if(a <= l && r <= b){findans = mod(findans + sum[Ind]); return; } LL mid = (l + r) >> 1;
    if(lazya[Ind] != 1 || lazyb[Ind] != 0) pushdown(l, r, Ind);
    if(a <= mid) { _Query(a, b, l, mid, Ind<<1); } if(b > mid) { _Query(a, b, mid + 1, r, (Ind<<1) + 1); }
    pushup(Ind);
}

inline void _Modify(LL a, LL b, LL l, LL r, LL Ind, LL d, bool f){
    if(a <= l && r <= b){ if(f){ sum[Ind] = mod(sum[Ind] * d); lazya[Ind] = mod(lazya[Ind] * d); lazyb[Ind] = mod(lazyb[Ind] * d); } else{ sum[Ind] = mod(sum[Ind] + mod((r - l + 1)*d)); //! lazyb[Ind] = mod(lazyb[Ind] + d); } return; } LL mid = (l + r) >> 1;
    if(lazya[Ind] != 1 || lazyb[Ind] != 0) pushdown(l, r, Ind);
    if(a <= mid){ _Modify(a, b, l, mid, Ind<<1, d, f); } if(b > mid){ _Modify(a, b, mid + 1, r, (Ind<<1) + 1, d, f); }
    pushup(Ind);
}

inline void Query(LL a, LL b) {return _Query(a, b, 1, sz, 1);}
inline void Modify(LL a,LL b,LL d, bool f){return _Modify(a, b, 1, sz, 1, d, f);}

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    LL T = 1;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    LL n, q, t, l, r, c, i;
    scanf("%lld%lld", &n, &MOD);
    sz = n;
    init();
    for(i = 1; i <= n; i++){
        scanf("%lld", &c);
        Modify(i, i, c, false);
    }

    scanf("%lld", &q);
    while(q--){
        scanf("%lld", &t);
        if(t == 1){
            scanf("%lld%lld%lld", &l, &r, &c);
            Modify(l, r, c, true);
        }
        else if(t == 2){
            scanf("%lld%lld%lld", &l, &r, &c);
            Modify(l, r, c, false);
        }
        else{
            scanf("%lld%lld", &l, &r);
            findans = 0;
            Query(l, r);
            printf("%lldn", findans);
        }
    }

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx