BZOJ 1798 (线段树||分块)的标记合并

我原来准备做方差的。。

结果发现不会维护两个标记。。

就是操作变成一个 a*x+b ，每次维护a ， b 即可

加的时候a=1 ，b=v

乘的时候a=v ，b=0

#include <cstdio>
const long long Maxn=100010;

long long a[Maxn],n,P,l,r,c,m,type;
struct Node
{
    long long mul,add,sum,len;
}tree[Maxn<<2];

inline void Change(long long o,long long mul,long long add)
{
    tree[o].mul=(tree[o].mul*mul)%P;
    tree[o].add=(tree[o].add*mul+add)%P;
    tree[o].sum=(tree[o].sum*mul+tree[o].len*add)%P;
}
inline void push_down(long long o)
{
    Change(o<<1,tree[o].mul,tree[o].add);
    Change(o<<1|1,tree[o].mul,tree[o].add);
    tree[o].mul=1; tree[o].add=0;
}
inline void push_up(long long o)
{
    tree[o].sum=(tree[o<<1].sum+tree[o<<1|1].sum)%P;
    tree[o].len=tree[o<<1].len+tree[o<<1|1].len;
}
void Build(long long o,long long l,long long r)
{
    tree[o].mul=1; tree[o].add=0;
    if (l==r) {tree[o].sum=a[l]; tree[o].len=1; return;}
    long long mid=(l+r)>>1;
    Build(o<<1,l,mid),Build(o<<1|1,mid+1,r);
    push_up(o);
}
void Mul(long long o,long long l,long long r,long long p,long long q,long long v)
{
    if (l==p && r==q)
    {
        Change(o,v,0);
        return;
    }
    push_down(o);
    long long mid=(l+r)>>1;
    if (q<=mid) Mul(o<<1,l,mid,p,q,v);
    if (p>=mid+1) Mul(o<<1|1,mid+1,r,p,q,v);
    if (p<=mid && q>=mid+1) 
        Mul(o<<1,l,mid,p,mid,v),Mul(o<<1|1,mid+1,r,mid+1,q,v);
    push_up(o);
}
void Add(long long o,long long l,long long r,long long p,long long q,long long v)
{
    if (l==p && r==q)
    {
        Change(o,1,v);
        return;
    }
    push_down(o);
    long long mid=(l+r)>>1;
    if (q<=mid) Add(o<<1,l,mid,p,q,v);
    if (p>=mid+1) Add(o<<1|1,mid+1,r,p,q,v);
    if (p<=mid && q>=mid+1) 
        Add(o<<1,l,mid,p,mid,v),Add(o<<1|1,mid+1,r,mid+1,q,v);
    push_up(o);
}
long long Sum(long long o,long long l,long long r,long long p,long long q)
{
    if (l==p && r==q) return tree[o].sum;
    long long mid=(l+r)>>1;
    push_down(o);
    if (q<=mid) return Sum(o<<1,l,mid,p,q);
    if (p>=mid+1) return Sum(o<<1|1,mid+1,r,p,q);
    if (p<=mid && q>=mid+1) 
        return (Sum(o<<1,l,mid,p,mid)+Sum(o<<1|1,mid+1,r,mid+1,q))%P;
}
int main()
{
    // freopen("c.in","r",stdin);
    scanf("%lld%lld",&n,&P);
    for (long long i=1;i<=n;i++) scanf("%lld",&a[i]);
    Build(1,1,n);
    scanf("%lld",&m);
    for (long long i=1;i<=m;i++)
    {
        scanf("%lld",&type);
        if (type==1) 
        {
            scanf("%lld%lld%lld",&l,&r,&c);
            Mul(1,1,n,l,r,c);
        }
        if (type==2) 
        {
            scanf("%lld%lld%lld",&l,&r,&c);
            Add(1,1,n,l,r,c);
        }
        if (type==3) 
        {
            scanf("%lld%lld",&l,&r);
            printf("%lld
",Sum(1,1,n,l,r));
        }
    }
    return 0;
}

 UPD:2016.6.14

突然发现好久没有写过分块了，想到这道可以分块，push_up写成push_down了..

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#define LL long long
using namespace std;
const LL Maxn=600010;
const LL Inf=0x3f3f3f3f;
LL a[Maxn],n,P,l,r,c,m,type,Block[Maxn];
struct Node
{
    LL mul,add,len,sum;
}tree[Maxn];
 
inline void Change(LL o,LL mul,LL add)
{
    tree[o].mul=(tree[o].mul*mul)%P;
    tree[o].add=(tree[o].add*mul+add)%P;
    tree[o].sum=(tree[o].sum*mul+tree[o].len*add)%P;
}
inline void push_down(LL o)
{
    for (;Block[o]==Block[o-1];o--);
    for (LL i=o;Block[o]==Block[i];i++) a[i]=(a[i]*tree[Block[i]].mul+tree[Block[i]].add)%P;
    tree[Block[o]].mul=1,tree[Block[o]].add=0;
}

inline void push_up(LL o)
{
    tree[Block[o]].sum=0;
    for (;Block[o]==Block[o-1];o--);
    for (LL i=o;Block[o]==Block[i];i++) tree[Block[o]].sum=(tree[Block[o]].sum+a[i])%P;
}
void Mul(LL p,LL q,LL v)
{
    if (Block[p]==Block[q])
    {
        push_down(p);
        for (LL i=p;i<=q;i++) a[i]=(a[i]*v)%P; 
        push_up(p);
        return;
    }
    for (LL i=Block[p]+1;i<Block[q];i++) Change(i,v,0);
    push_down(p),push_down(q);
    for (LL i=p;Block[i]==Block[p];i++) a[i]=(a[i]*v)%P;
    for (LL i=q;Block[i]==Block[q];i--) a[i]=(a[i]*v)%P;
    push_up(p),push_up(q);
}

void Add(LL p,LL q,LL v)
{
    if (Block[p]==Block[q])
    {
        push_down(p);
        for (LL i=p;i<=q;i++) a[i]=(a[i]+v)%P; 
        push_up(p);
        return;
    }
    for (LL i=Block[p]+1;i<Block[q];i++) Change(i,1,v);
    push_down(p),push_down(q);
    for (LL i=p;Block[i]==Block[p];i++) a[i]=(a[i]+v)%P;
    for (LL i=q;Block[i]==Block[q];i--) a[i]=(a[i]+v)%P;
    push_up(p),push_up(q);
}
LL Sum(LL p,LL q)
{
    LL ret=0;
    if (Block[p]==Block[q]) 
    {
        push_down(p);
        for (LL i=p;i<=q;i++) ret=(ret+a[i])%P;
        return ret;
    }
    for (LL i=Block[p]+1;i<Block[q];i++) ret=(ret+tree[i].sum)%P;
    push_down(p),push_down(q);
    for (LL i=p;Block[i]==Block[p];i++) ret=(ret+a[i])%P;
    for (LL i=q;Block[i]==Block[q];i--) ret=(ret+a[i])%P;
    return ret;
}
int main()
{
    scanf("%lld%lld",&n,&P);
    for (LL i=1;i<=n;i++) scanf("%lld",&a[i]),a[i]%=P;
    LL pos=(LL)sqrt(n);
    for (LL i=1;i<=n;i++) Block[i]=(i-1)/pos+1;
    memset(tree,0,sizeof(tree));
    for (LL i=1;i<=n;i++) tree[Block[i]].len++;
    for (LL i=1;i<=n;i++) tree[Block[i]].mul=1;
    for (LL i=1;i<=n;i++) tree[Block[i]].sum=(tree[Block[i]].sum+a[i])%P;

    scanf("%lld",&m);
    for (LL i=1;i<=m;i++)
    {
        scanf("%lld",&type);
        if (type==1) 
        {
            scanf("%lld%lld%lld",&l,&r,&c);
            Mul(l,r,c);
        }
        if (type==2) 
        {
            scanf("%lld%lld%lld",&l,&r,&c);
            Add(l,r,c);
        }
        if (type==3) 
        {
            scanf("%lld%lld",&l,&r);
            printf("%lld
",Sum(l,r));
        }
    }
    return 0;
}