题解：P13982 数列分块入门 7

· · 题解

虽然是分块题，但是为什么不能用线段树【笑】。

区间加，区间乘，单点询问。如果用线段树的话，那么懒标记就很重要。
这里有两个操作，因此要有两个懒标记，一个是乘法，一个是加法。
那么懒标记的下传便有一点讲究了，你需要搞清楚它的优先级。

以下记 laz_1 表示乘法的懒标记，laz_2 表示加法的懒标记。
由于乘法优先级大于加法，因此首先下传乘法标记。
此时，左右儿子的 laz_1、laz_2 和 sum 都要乘上当前的 laz_1。
然后下传加法标记，此时只需要把左右儿子的 laz_2 更新。

然后就和普通的区间修改、区间查询一样了。
本题数据较为毒瘤，多模几次。 

#include<stdio.h>
const int mod=10007;
long long n,sr,a,b,c,d;
long long che[1200005],sum[1200005],plus[1200005];
void up(int rt){sum[rt]=((sum[rt<<1]+sum[rt<<1|1])%mod+mod)%mod;}
void down(int rt,long long l,long long r)
{
    long long mid=(l+r)/2;
    if(che[rt]!=1) che[rt<<1]=che[rt<<1]*che[rt]%mod,
    plus[rt<<1]=plus[rt<<1]*che[rt]%mod,
    che[rt<<1|1]=che[rt<<1|1]*che[rt]%mod,
    plus[rt<<1|1]=plus[rt<<1|1]*che[rt]%mod,
    sum[rt<<1]=sum[rt<<1]*che[rt]%mod,
    sum[rt<<1|1]=sum[rt<<1|1]*che[rt]%mod,
    che[rt]=1;
    if(plus[rt]) plus[rt<<1]=(plus[rt<<1]+plus[rt])%mod,
    plus[rt<<1|1]=(plus[rt<<1|1]+plus[rt])%mod,
    sum[rt<<1]=(sum[rt<<1]+(mid-l+1)*plus[rt]%mod)%mod,
    sum[rt<<1|1]=(sum[rt<<1|1]+(r-mid)*plus[rt]%mod)%mod,
    plus[rt]=0;
    sum[rt<<1]=(sum[rt<<1]+mod)%mod,che[rt<<1]=(che[rt<<1]+mod)%mod,
    plus[rt<<1]=(plus[rt<<1]+mod)%mod;
    sum[rt<<1|1]=(sum[rt<<1|1]+mod)%mod,che[rt<<1|1]=(che[rt<<1|1]+mod)%mod,
    plus[rt<<1|1]=(plus[rt<<1|1]+mod)%mod;
}
void add(int rt,long long l,long long r,int ll,int rr,int typ,long long num)
{
    if(r<ll||rr<l) return;
    if(ll<=l&&r<=rr)
    {
        if(typ) che[rt]=che[rt]*num%mod,plus[rt]=plus[rt]*num%mod,sum[rt]=sum[rt]*num%mod;
        else plus[rt]=(plus[rt]+num)%mod,sum[rt]=(sum[rt]+(r-l+1)*num%mod)%mod;
        sum[rt]=(sum[rt]+mod)%mod,che[rt]=(che[rt]+mod)%mod,plus[rt]=(plus[rt]+mod)%mod;
        return;
    }down(rt,l,r),add(rt<<1,l,(l+r)/2,ll,rr,typ,num),
    add(rt<<1|1,(l+r)/2+1,r,ll,rr,typ,num),up(rt); 
}
long long ask(int rt,long long l,long long r,int wh)
{
    if(l==r) return sum[rt];down(rt,l,r);
    if(wh<=(l+r)/2) return ask(rt<<1,l,(l+r)/2,wh);
    return ask(rt<<1|1,(l+r)/2+1,r,wh);
}
int main()
{
    scanf("%lld",&n);for(int i=1;i<=4*n;i++) che[i]=1;
    for(int i=1;i<=n;i++) scanf("%lld",&sr),add(1,1,n,i,i,0,sr);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        if(a!=2) add(1,1,n,b,c,a,d);
        else printf("%lld\n",ask(1,1,n,c));
    }
}