这里问题的关键是妥善处理好两种标记
让乘法标记的优先级高于加法
若当前的一个块乘以m1后加上a1,这时进行一个乘m2的操作,则原来的标记变成m1*m2,a1*m2
若当前的一个块乘以m1后加上a1,这时进行一个加a2的操作,则原来的标记变成m1,a1+a2
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=100005; 6 const int mod=10007; 7 int n,blo; 8 int v[maxn],bl[maxn],atag[1005],mtag[1005]; 9 long long read()10 {11 long long x=0,f=1;char ch=getchar();12 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();}13 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}14 return x*f;15 }16 void reset(int x)17 {18 for(int i=(x-1)*blo+1;i<=min(n,x*blo);i++)19 v[i]=(v[i]*mtag[x]+atag[x])%mod;20 atag[x]=0;mtag[x]=1;21 }22 void solve(int f,int a,int b,int c)23 {24 reset(bl[a]);25 for(int i=a;i<=min(bl[a]*blo,b);i++)26 {27 if(f==0) v[i]+=c;28 else v[i]*=c;29 v[i]%=mod;30 }31 if(bl[a]!=bl[b])32 {33 reset(bl[b]);34 for(int i=(bl[b]-1)*blo+1;i<=b;i++)35 {36 if(f==0) v[i]+=c;37 else v[i]*=c;38 v[i]%=mod;39 }40 }41 for(int i=bl[a]+1;i<=bl[b]-1;i++)42 {43 if(f==0) atag[i]=(atag[i]+c)%mod;44 else45 {46 atag[i]=(atag[i]*c)%mod;47 mtag[i]=(mtag[i]*c)%mod;48 }49 }50 }51 int main()52 {53 n=read();blo=sqrt(n);54 for(int i=1;i<=n;i++) v[i]=read();55 for(int i=1;i<=n;i++) bl[i]=(i-1)/blo+1;56 for(int i=1;i<=bl[n];i++) mtag[i]=1;57 for(int i=1;i<=n;i++)58 {59 int f=read(),a=read(),b=read(),c=read();60 if(f==2) printf("%d\n",(v[b]*mtag[bl[b]]+atag[bl[b]])%mod);61 else solve(f,a,b,c);62 }63 return 0;64 }