#6283. 数列分块入门 7

题目链接：https://loj.ac/problem/6283

给出一个长为

第一行输入一个数字

第二行输入 $aia_iai，以空格隔开。$

接下来输入

若

对于每次询问，输出一行一个数字表示答案。

样例输入

7
1 2 2 3 9 3 2
0 1 3 1
2 1 3 1
1 1 4 4
0 1 7 2
1 2 6 4
1 1 6 5
2 2 6 4

样例输出

3
100

思路：容易知道加法操作会影响乘法操作的值。
但我们可以用sum[]存整块的加数，m[]存整块的乘的系数。容易知道，乘的时候sum也要乘。
比如：
数值x第一个操作加c1,数值变成了x+c1。用sum[]存c1;
第二个操作乘以c2，数值变成(x+c1)*c2,可以理解为c2*x+c1*c2，用sum[]存c1*c2,m[]存c2。

但要注意不完整块的处理，每次不完整的块要更新a[]的值，因为可能前面的操作把它当成完整块处理了，
不完整块要暴力加嘛，所以要变成最新的值才可以暴力加，只有始终为完整块的数可以不用更新.

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
const int mod=10007;
ll n,a[maxn],pos[maxn],m[maxn],sum[maxn],block; 

void reset(int x)//更新不完整块中的每个值 
{
    ll p=pos[x];
    for(int i=(p-1)*block+1;i<=min(p*block,n);i++)
        a[i]=(m[p]*a[i]+sum[p])%mod;
    m[p]=1,sum[p]=0;//记得更新该快的sum,m; 
}
void update(int l,int r,int c,int opt)//加和乘 
{
    reset(l);//更新左边不完整块 
    for(int i=l;i<=min(pos[l]*block,(ll)r);i++)//暴力加或乘 
    {
        if(opt==0)
            a[i]=(a[i]+c)%mod;
        else
            a[i]=(a[i]*c)%mod;
    }
    if(pos[l]!=pos[r])
    {
        reset(r);//更新右边不完整块 
        for(int i=(pos[r]-1)*block+1;i<=r;i++)//暴力加或乘 
            if(opt==0)
                a[i]=(a[i]+c)%mod;
            else
                a[i]=(a[i]*c)%mod;
    }
    for(int i=pos[l]+1;i<=pos[r]-1;i++)//完整块处理 
        if(opt==0)
            sum[i]=(sum[i]+c)%mod;//加 
        else//乘 
        {
            sum[i]=(sum[i]*c)%mod;//sum要乘  关键 
            m[i]=(m[i]*c)%mod;//系数要乘 
        }
}

int main()
{
    scanf("%d",&n);
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]%=mod;
        pos[i]=(i-1)/block+1;
        m[pos[i]]=1;//系数初始化为1 
    }
    int opt,l,r,c;
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&opt,&l,&r,&c);
        if(opt==0||opt==1)
            update(l,r,c,opt);
        else 
            printf("%lld
",(a[r]*m[pos[r]]+sum[pos[r]])%mod);
    }
    return 0;
}

#6283. 数列分块入门 7

题目描述

输入格式

输出格式

样例

样例输入

样例输出