题解：P13979 数列分块入门 4
前言
分块入门题，但是细节比较多。
思路
思路 1 ：分块
首先，你要保证你会数列分块入门
这道题和数列分块入门
可以发现，如果我们要统计一个完整块的答案，那么我们只用我的上面那篇题解中“块的权值”肯定是不够的。
因为在修改过程中可能这一块有一部分是暴力修改的，而这个暴力修改的影响是不会计入到“块的权值”的。解决方法也很简单：再定义一个数组，表示这个块内所有数的和（后面简称块的和），这个问题就迎刃而解了。
具体维护方式：如果是暴力修改，那么每修改一个数，就把这个位置对应块的和也修改一次；如果是整个块整体修改，那么就每修改一个块，这个块的和加上增加的值乘以块的长度，注意：可能有角块，有的写法注意角块和正常块长度不同。
再看查询部分。如果查询的部分中有一些完整的块的话，那么直接将这些块的和累加。否则暴力计算答案，其实就相当于单点查询。注意：暴力计算答案时一定要把这个块的权值加上！
单次修改或查询时间复杂度：
如果还不能理解的话可以看代码理解。代码中有详细注释。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[300005],num[555],sum[555];//num[i]：第i个块的权值 sum[i]：第i个块所对应原数组中的数之和。
signed main() {
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int len;
len = sqrt(n);//每个块的长度
for(int i = 1; i<=n; i++) {
cin>>a[i];
sum[(i-1)/len+1] = sum[(i-1)/len+1]+a[i];
}
for(int i = 1; i<=n; i++) {
int op,l,r,c;
cin>>op>>l>>r>>c;
int nl,nr;//起点和终点所在块
nl = (l-1)/len+1;
nr = (r-1)/len+1;
if(!op) {
if(nl == nr) { //细节：如果起点和终点在一个块，那么直接暴力修改
for(int j = l; j<=r; j++) {
a[j] = a[j]+c;
sum[nl] = sum[nl]+c;//暴力修改，把块的和一起修改
}
} else {
for(int j = l; j<=nl*len; j++) { //暴力修改起点到起点所在块的末尾部分
a[j] = a[j]+c;
sum[nl] = sum[nl]+c;
}
for(int j = nl+1; j<nr; j++) { //修改中间完整块的部分
num[j] = num[j]+c;
sum[j] = sum[j]+len*c;//整个区间修改。由于本人写法问题，最后一个角块一定不会当成完整的块修改。注意最后一个角块的长度与其他块不同。
}
for(int j = (nr-1)*len+1; j<=r; j++) { //暴力修改终点所在块的开头到终点的部分
a[j] = a[j]+c;
sum[nr] = sum[nr]+c;
}
}
} else {//同理
c++;
int ans;
ans = 0;
if(nl == nr){
for(int j = l;j<=r;j++){
ans = ans+a[j]+num[nl];//注意加上块的权值
}
}else{
for(int j = l; j<=nl*len; j++) {
ans = ans+a[j]+num[nl];
}
for(int j = nl+1; j<nr; j++) {
ans = ans+sum[j];
}
for(int j = (nr-1)*len+1; j<=r; j++) {
ans = ans+a[j]+num[nr];
}
}
ans = (ans%c+c)%c;
cout<<ans<<"\n";
}
}
return 0;
}
思路 2 ：树状数组
这道题是很经典的区间修改区间查询，其实就是守墓人。由于树状数组不是本题重点，所以不在此详细讲述。不会的可以自学一下，
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[300005],tr1[300005],tr2[300005],n,m;
int lowbit(int now){
return now&(-now);
}
void update(int w,int num){
for(int i = w;i<=n;i = i+lowbit(i)){
tr1[i] = tr1[i]+num;
tr2[i] = tr2[i]+num*(w-1);
}
}
int find(int w){
int ans;
ans = 0;
for(int i = w;i;i = i-lowbit(i)){
ans = ans+tr1[i]*w-tr2[i];
}
return ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i = 1;i<=n;i++){
cin>>a[i];
update(i,a[i]-a[i-1]);
}
for(int i = 1;i<=n;i++){
int op,l,r,k;
cin>>op>>l>>r>>k;
if(!op){
update(l,k);
update(r+1,-k);
}else{
k++;
cout<<((find(r)-find(l-1))%k+k)%k<<"\n";
}
}
return 0;
}
思路 3 ：线段树
其实这道题就是线段树
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int l,r,num,len,tag;
}a[1200005];
int b[300005],n;
void pushup(int now){
a[now].num = a[now*2].num+a[now*2+1].num;
}
void build(int now,int l,int r){
a[now].l = l;
a[now].r = r;
a[now].len = r-l+1;
if(l == r){
a[now].num = b[l];
return;
}
int mid;
mid = (l+r)/2;
build(now*2,l,mid);
build(now*2+1,mid+1,r);
pushup(now);
}
void pushdown(int now){
a[now*2].tag = a[now*2].tag+a[now].tag;
a[now*2].num = a[now*2].num+a[now*2].len*a[now].tag;
a[now*2+1].tag = a[now*2+1].tag+a[now].tag;
a[now*2+1].num = a[now*2+1].num+a[now*2+1].len*a[now].tag;
a[now].tag = 0;
}
void update(int now,int l,int r,int cg){
if(a[now].l>r || a[now].r<l){
return;
}
if(l<=a[now].l && a[now].r<=r){
a[now].num = a[now].num+a[now].len*cg;
a[now].tag = a[now].tag+cg;
return;
}
pushdown(now);
update(now*2,l,r,cg);
update(now*2+1,l,r,cg);
pushup(now);
}
int find(int now,int l,int r){
if(a[now].l>r || a[now].r<l){
return 0;
}
if(l<=a[now].l && a[now].r<=r){
return a[now].num;
}
pushdown(now);
int ans;
ans = find(now*2,l,r)+find(now*2+1,l,r);
pushup(now);
return ans;
}
signed main() {
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i = 1;i<=n;i++){
cin>>b[i];
}
build(1,1,n);
for(int i = 1;i<=n;i++){
int op,l,r,k;
cin>>op>>l>>r>>k;
if(!op){
update(1,l,r,k);
}else{
k++;
cout<<(find(1,l,r)%k+k)%k<<"\n";
}
}
return 0;
}
坑点
注意取模！模数是