【线段树】【BZOJ1798】【AHOI2009】维护序列

还是那个学弟@lher出的丧题之一。

链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1798

题意简析：就是题目啊。。。

解题思路：显然是线段树啊。。。根据乘法分配律处理一下区间乘法操作，其他就是简单的区间加法查询，很水吧owo。时间效率\(O(m \lg n) \)。

附AC代码：

#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
#define mid ((l+r)>>1)
#define ls (k<<1)
#define rs (k<<1|1)
using namespace std;
struct zxy{
    ll val,mult,add;
}tr[];
int n,mod,q;
inline int in(){
    int x=,f=;
    char ch=getchar();
    while(ch<''||ch>'') {if(ch=='-') f=-; ch=getchar();}
    while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
    return x*f;
}
inline void pushdown(int k,int l,int r){
    if (tr[k].mult==&&!tr[k].add) return;
    int D=(r-l)+;
    tr[ls].add=(tr[ls].add*tr[k].mult+tr[k].add)%mod;
    tr[rs].add=(tr[rs].add*tr[k].mult+tr[k].add)%mod;
    tr[ls].mult=(tr[ls].mult*tr[k].mult)%mod;
    tr[rs].mult=(tr[rs].mult*tr[k].mult)%mod;
    tr[ls].val=(tr[ls].val*tr[k].mult+(D-(D>>))*tr[k].add)%mod;
    tr[rs].val=(tr[rs].val*tr[k].mult+(D>>)*tr[k].add)%mod;
    tr[k].mult=,tr[k].add=;
}
inline void combine(int k){
    tr[k].val=(tr[ls].val+tr[rs].val)%mod;
}
inline void update(int k,int l,int r,int a,int b,int mult,int add){
    if (l>=a&&r<=b){
        tr[k].mult=tr[k].mult*mult%mod;
        tr[k].add=(tr[k].add*mult+add)%mod;
        tr[k].val=(tr[k].val*mult+(r-l+)*add)%mod;
        return;
    }
    pushdown(k,l,r);
    if (a<=mid) update(ls,l,mid,a,b,mult,add);
    if (b>mid) update(rs,mid+,r,a,b,mult,add);
    combine(k);
}
inline ll query(int k,int l,int r,int a,int b){
    if (l==a&&r==b) return tr[k].val%mod;
    pushdown(k,l,r);
    if (b<=mid) return query(ls,l,mid,a,b);
    if (a>mid) return query(rs,mid+,r,a,b);
    return (query(ls,l,mid,a,mid)+query(rs,mid+,r,mid+,b))%mod;
}
inline void built(int k,int l,int r){
    tr[k].mult=; tr[k].add=;
    if(l==r) {
        tr[k].val=in();
        return;
    }
    built(ls,l,mid);built(rs,mid+,r);
    combine(k);
}
int main(){
    n=in(),mod=in();    built(,,n);
    q=in();
    for (register int i=; i<=q; ++i){
        int typ=in(),l=in(),r=in();
        if (typ==) update(,,n,l,r,,in());
        if (typ==) update(,,n,l,r,in(),);
        if (typ==)printf("%lld\n",query(,,n,l,r));
    }
    return ;
}

本文由Melacau编写，Melacau代表M星向您问好，如果您不是在我的博客http://www.cnblogs.com/Melacau上看到本文，请您向我联系，email:[e-mail].