[Ynoi2011] 初始化
第一道通过的 Ynoi 题，虽然似乎大概也许并不太难。
题目分析
查询操作为求区间和，可以使用分块。
看到这种修改操作满足“跳着加”性质的题目，可以尝试根号分治。
那么如何进行根号分治呢？
当 \(x \ge \sqrt{n}\) 时，需要修改的位置最多有 \(\sqrt{n}\) 个，故可以暴力地修改。
当 \(x < \sqrt{n}\) 时，需要使用另外一种方式维护：
观察需要修改的位置不难发现，假如我们把原数列分成块长为 \(x\) 的若干个块，那么修改操作相当于在每个块内的第 \(y\) 个位置上加 \(z\)，定义 \(f_{i,j}\) 表示当 \(x=i\) 时，每个块内的第 \(j\) 个位置上一共被加了多少，然后定义 \(add_{i,j}\) 满足 \(add_{i,j}=\sum^{j}_{k=1}f_{i,k}\)，于是查询操作的结果可以表示为：
\[\sum^r_{i=l}a_{i}+\sum^{\sqrt{n}}_{i=1}(add_{i,i} \times (\lfloor \frac{r}{i} \rfloor - \lfloor \frac{l-1}{i} \rfloor) + add_{i,r \bmod i} - add_{i,(l-1) \bmod i}) \]其中，\(\sum^r_{i=l}a_{i}\) 可以通过分块快速求出。
卡常小技巧：本题的需要维护的各种数据都不会超过 long long 类型的上限，所以对于查询操作，可以在求得结果后再进行取模。
部分代码
inline void change(int x,int y,int z){
if(x>=t){
for(register int i=y;i<=n;i+=x){
a[i]+=z;
sum[pos[i]]+=z;
}
}
else for(register int i=y;i<=x;i++) add[x][i]+=z;
}
inline long long ask(int l,int r){
long long ans=0;
int p=pos[l],q=pos[r];
if(p==q){
for(register int i=l;i<=r;i++){
ans+=a[i];
}
}
else{
for(register int i=p+1;i<=q-1;i++) ans+=sum[i];
for(register int i=l;i<=R[p];i++) ans+=a[i];
for(register int i=L[q];i<=r;i++) ans+=a[i];
}
for(register int i=1;i<=t;i++){
ans+=add[i][i]*(r/i-(l-1)/i)+add[i][r%i]-add[i][(l-1)%i];
}
return ans;
}
int main(){
n=read();
m=read();
for(register int i=1;i<=n;i++) a[i]=read();
t=sqrt(n);
for(register int i=1;i<=t;i++){
L[i]=(i-1)*t+1;
R[i]=i*t;
}
if(R[t]<n){
t++;
L[t]=R[t-1]+1;
R[t]=n;
}
for(int i=1;i<=t;i++){
for(int j=L[i];j<=R[i];j++){
pos[j]=i;
sum[i]+=a[j];
}
}
while(m--){
int t1=read();
if(t1==1){
int t2=read(),t3=read(),t4=read();
change(t2,t3,t4);
}
else{
int t2=read(),t3=read();
write(ask(t2,t3)%mod);
putchar('\n');
}
}
return 0;
}