给出一个长为 的数列。
有 个询问，每行输入四个数字 、、、，以空格隔开。
若 ，表示将位于 的之间的数字都加 。
若 ，表示询问 的值（ 和 忽略）。
保证 。。每次操作后的 满足 。
考虑暴力。
我们可以按题目说的模拟，每次遍历 加， 就输出 ，复杂度 ，明显无法通过。
考虑复杂度正确的做法。
我们可以将数组分成一段一段的“块”。
就像这样：
对于每一个块，我们可以去维护它块内元素的和。在求区间加的时候，对于“不完整”的块直接暴力加，中间的“完整块”打上一个懒标记。这样在求 的值的时候，只需要用 加上 所在块的懒标记了。
时间复杂度 。
这个思想听上去不错，但仍然有一些小细节。
如何计算下标对应的块编号？
我们设预定块长为 ，则编号为 。是什么意思呢？我们先将下标转换为 开头的，这样 就是从 开始的块编号，加一就是 开头的了。
如果 不是 的倍数怎么办？
其实最后一个块不一定是完整的，不影响计算。
块长怎么确定？
块长最好是 。
不难发现上述操作区间修改的时间复杂度是 的。
由二元均值不等式，对 有：
令 ，代入得：
等号成立条件：
所以最优块长为 。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+7;
int a[N],b[N],id[N],n,len,s[N];
void add(int l,int r,int x){
if(id[l]==id[r]){
for(int i=l;i<=r;i++)a[i]+=x,s[id[l]]+=x;//同一块暴力加
return;
}
for(int i=l;id[i]==id[l];i++)a[i]+=x,s[id[l]]+=x;//左边“不完整块”暴力加
for(int i=id[l]+1;i<id[r];i++)b[i]+=x,s[i]+=len*x;//中间大块打懒标记，更新块内元素和
for(int i=r;id[i]==id[r];i--)a[i]+=x,s[id[r]]+=x;//右边“不完整块”暴力加
}
signed main(){
cin>>n;
len=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];
id[i]=(i-1)/len+1;
s[id[i]]+=a[i];
}
for(int i=1;i<=n;i++){
int opt,l,r,c;
cin>>opt>>l>>r>>c;
if(opt==0)add(l,r,c);
else print("{}\n",a[r]+b[id[r]]);//求值
}
}
共 1 条评论
注意：std::print 在 C++23 中引入