[DS记录]P5309 [Ynoi2011]初始化
command_block
·
·
个人记录
题意 ： 维护一个序列 A ，支持下列两种操作。
------------
根号分治经典题目。
- 当 $x>\sqrt{n}$ 时，被修改的位置不超过 $\sqrt{n}$ 个。
可以使用 $O(1)$ 修改 $O(\sqrt{n})$ 查询的分块。
- 当 $x\leq \sqrt{n}$ 时，考虑对每个不同的 $x$ 计算贡献。
我们将序列分成大小为 $x$ 的块，若某一块被 $[l,r]$ 完整包含，贡献显然是 $y$ 的和。
对于两端的散块，贡献是 $y$ 的前缀或后缀和。此时 $y\leq x\leq \sqrt{n}$ ，暴力维护即可。
总复杂度 $O(n\sqrt{n})$。
第二部分常数较大，可以把阈值调小一点。
```cpp
#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
#define MaxN 200500
using namespace std;
int read(){
int X=0;char ch=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return X;
}
const int mod=1000000007;
struct SumDS
{
int BS;
ll o[MaxN],s[505];
inline void add(int p,int c)
{o[p]+=c;s[p/BS]+=c;}
int qry(int p)
{
ll ret=0;int bp=p/BS;
for (int i=0;i<bp;i++)
ret=(ret+s[i])%mod;
for (int i=bp*BS;i<=p;i++)
ret+=o[i];
return ret%mod;
}
}T;
ll S[105][105];
int n,m,BS;
int main()
{
n=read();m=read();
T.BS=sqrt(n)+2;
BS=pow(n,0.375)+2;
for (int i=1,u;i<=n;i++)
T.add(i,read());
for (int i=1,op;i<=m;i++){
op=read();
if (op==1){
int x=read(),y=read()%x,c=read();
if (x>BS)
for (int j=y;j<=n;j+=x)
T.add(j,c);
else
for (int j=y;j<x;j++)
S[x][j]+=c;
}else {
int l=read(),r=read();
ll ret=T.qry(r)-T.qry(l-1);
for (int x=1;x<=BS;x++){
ret+=S[x][x-1]%mod*(r/x-l/x);
ret+=S[x][r%x]-(l%x ? S[x][l%x-1] : 0);
}printf("%lld\n",(ret%mod+mod)%mod);
}
}return 0;
}
```