数列分块入门 7
链接：LibreOj6283
题目描述
给出一个长为n的数列，以及n个操作，操作涉及区间乘法，区间加法，单点询问。
输入格式
第一行输入一个数字n。
第二行输入n个数字，第i个数字为 a[i]，以空格隔开。
接下来输入n行询问，每行输入四个数字op、l、r、c，以空格隔开。
若 op==0，将[l,r]之间的数字都加c
若 op==1，表示询问[l,r]所有数字都乘c
若op==2，表示询问a[r]的数值
输出对10007取模
输出格式
对于每次询问，输出一行一个数字表示答案。
样例输入
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
分析：
如果只有区间乘法的话，其实和区间加法难度是一样的。 但是两者都有，两者会互相影响. 这题显然要维护加法标记add和乘法标记mul 假设a[i]的数值为a，mul为b，add为c 那么a[i]实际数值为ab+c 1：如果我们要加一个数字d 则变为ab+(c+d) 如果是完整块操作只需要把add+=val 2：如果我们要乘一个数字d 则变为abd+(cd) 如果是完整块操作只需要把add*=val并且mul*=val
但是如果是不完整块的操作呢，mul和add是块属性，因为块内个别数据修改而修改mul和add显然会使得块内其他数据错误。 解决方法就是 先直接暴力把不完整块的数据全部算出来，即a[i]=ab+c，然后mul重置为1，add重置为0；接着暴力操作区间[l,r]的数据（直接a[i]加val或者a[i]乘val)。（最多操作2*根号n的数据）
我的代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<algorithm>
#include<sstream>
#include<memory>
#include<utility>
#include<functional>
#include<iterator>
typedef long long ll
;
const int inf
=0x3f3f3f3f;
const int inn
=0x80808080;
using namespace std
;
const int maxm
=1e5+5;
int mod
=10007;
int n
;
int a
[maxm
],add
[maxm
],mul
[maxm
];
int l
[maxm
],r
[maxm
];
int belong
[maxm
];
int block
,num
;
int d
,x
,y
,c
;
void build(){
block
=sqrt(n
);
num
=n
/block
;
if(n
%block
)num
++;
for(int i
=1;i
<=num
;i
++){
add
[i
]=0;
mul
[i
]=1;
l
[i
]=(i
-1)*block
+1;
r
[i
]=i
*block
;
}
r
[num
]=n
;
}
void reset(int node
){
for(int i
=l
[node
];i
<=r
[node
];i
++){
a
[i
]=(a
[i
]*mul
[node
]+add
[node
])%mod
;
}
mul
[node
]=1;
add
[node
]=0;
}
void update(int x
,int y
,int val
){
if(belong
[x
]==belong
[y
]){
reset(belong
[x
]);
for(int i
=x
;i
<=y
;i
++){
if(d
==0){
a
[i
]=(a
[i
]+val
)%mod
;
}else{
a
[i
]=(a
[i
]*val
)%mod
;
}
}
return ;
}
reset(belong
[x
]);
reset(belong
[y
]);
for(int i
=x
;i
<=r
[belong
[x
]];i
++){
if(d
==0){
a
[i
]=(a
[i
]+val
)%mod
;
}else{
a
[i
]=(a
[i
]*val
)%mod
;
}
}
for(int i
=l
[belong
[y
]];i
<=y
;i
++){
if(d
==0){
a
[i
]=(a
[i
]+val
)%mod
;
}else{
a
[i
]=(a
[i
]*val
)%mod
;
}
}
for(int i
=belong
[x
]+1;i
<belong
[y
];i
++){
if(d
==0){
add
[i
]+=val
;
}else{
add
[i
]=(add
[i
]*val
)%mod
;
mul
[i
]=(mul
[i
]*val
)%mod
;
}
}
}
int main(){
scanf("%d",&n
);
build();
for(int i
=1;i
<=n
;i
++){
belong
[i
]=(i
-1)/block
+1;
scanf("%d",&a
[i
]);
}
for(int i
=1;i
<=n
;i
++){
scanf("%d%d%d%d",&d
,&x
,&y
,&c
);
if(d
==0||d
==1){
update(x
,y
,c
);
}else{
printf("%d\n",(a
[y
]*mul
[belong
[y
]]+add
[belong
[y
]])%mod
);
}
}
return 0;
}
