2023NOIP A层联测32 T4 红楼 ~ Eastern Dream
根号分治加分块。
Ps：分块后面真的用的多。
思路
考虑根号分治，将 \(x\) 分为 \(x \leq \sqrt n\) 的情况和 \(x>\sqrt n\) 的情况。
\(x \leq \sqrt n\)
由于这一部分较小，如果在线段上暴力添加肯定会超时。
先设 \(f_{x,i}\) 表示模 \(x\) 等于 \(i\) 的数加的值，这个值可以每次暴力维护，时间 \(O(\sqrt n)\)。
再维护一个 \(f_x\) 的前缀和，也是 \(O(\sqrt n)\)。
每次查询时，枚举 \(x\)，求 \([l,r]\) 中有几个 \(x\) 余数的整段。
对于整段，可以直接乘求贡献；对于区间前后的零散段，可以通过前缀和求贡献。
这一部分的维护和查询均 \(O(\sqrt n)\)。
\(x>\sqrt n\)
对于修改操作，直接去暴力跳原数列上的 \(\frac{n}{x}\) 段去区间修改，对于一段使用线段树可以达到 \(\log n\) 的效果，但是有最多 \(\sqrt n\) 段，所以说没一段必须要 \(O(1)\) 修改，而查询可以支持 \(O(\sqrt n)\)。
不难想到可以分块，对于整数段可以直接加上一个值，对于零散块可以差分。由于每一段最多访问 \(2\) 次，所以复杂度可以保证在 \(O(\sqrt n)\)。
总结一下，对于 \(x \leq \sqrt n\) 的情况，更改维护 \(f_x\) 的前缀和，查询直接暴力加查询区间的值。
对于 \(x>\sqrt n\) 的情况，使用分块维护更改，查询也直接加查询区间内的块就 OK。
时间复杂度 \(O(m\sqrt n)\)。
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5,maxm=1000;
int n,m,block,a[maxn],L[maxn],R[maxn];
ll sum[maxm],c[maxn],pub[maxn],f[maxm][maxm],fs[maxm][maxm];
namespace IO{
#define BF_SIZE 100000
bool IOerr=0;
inline char nc(){
static char buf[BF_SIZE],*p1=buf+BF_SIZE,*pend=buf+BF_SIZE;
if(p1==pend){
p1=buf;
pend=buf+fread(buf,1,BF_SIZE,stdin);
if(pend==p1){IOerr=1;return -1;}
}
return *p1++;
}
inline bool bla(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline void Rd(int &x){
char ch;
while(bla(ch=nc()));
if(IOerr){return;}
for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0');
}
inline void Rd(ll&x){
char ch;
while(bla(ch=nc()));
if(IOerr){return;}
for(x=ch-'0';(ch=nc())>='0'&&ch<='9';x=x*10+ch-'0');
}
#undef BF_SIZE
};
inline void write(ll X)
{
if(X<0) {X=~(X-1); putchar('-');}
if(X>9) write(X/10);
putchar(X%10+'0');
}
inline void ycl()
{
for(int i=1;i<=n;i++)
{
int id=(i-1)/block;
sum[id]+=a[i];
}
}
int main()
{
IO::Rd(n), IO::Rd(m);
block=max((int)sqrt(n/4),1);
for(int i=1;i<=n;i++) IO::Rd(a[i]);
for(int i=0;i<=(n-1)/block;i++) L[i]=block*i+1,R[i]=block*i+block;
ycl();
for(int o=1;o<=m;o++)
{
int op,x,y;
ll k;
IO::Rd(op);IO::Rd(x);IO::Rd(y);
if(op==2)
{
int l=x,r=y;
ll ans=0;
for(int i=1;i<=block;i++)
{
int tl=(l-1)%i,tr=(r-1)%i;
int ml=(l-1)/i,mr=(r-1)/i;
if(ml==mr) ans+=fs[i][tr+1]-fs[i][tl];
else
{
ans+=(mr-ml-1)*fs[i][i];
ans+=fs[i][i]-fs[i][tl];
ans+=fs[i][tr+1];
}
}
int idl=(l-1)/block,idr=(r-1)/block;
if(idl==idr)
{
ll cj=0;
for(int i=L[idl];i<l;i++) cj+=c[i];
for(int i=l;i<=r;i++)
{
cj+=c[i];
ans+=cj+pub[idl]+a[i];
}
}
else
{
ll cj=0;
for(int i=L[idl];i<l;i++) cj+=c[i];
for(int i=l;i<=R[idl];i++)
{
cj+=c[i];
ans+=cj+pub[idl]+a[i];
}
for(int i=idl+1;i<idr;i++) ans+=sum[i];
cj=0;
for(int i=L[idr];i<=r;i++)
{
cj+=c[i];
ans+=cj+pub[idr]+a[i];
}
}
write(ans);
putchar('\n');
continue;
}
IO::Rd(k);
y=min(y,x-1);
if(x<=block)
{
for(int i=1;i<=y+1;i++) f[x][i]+=k;
for(int i=1;i<=x;i++) fs[x][i]=fs[x][i-1]+f[x][i];
}
else
{
for(int i=1;i<=n;i+=x)
{
int l=i,r=i+y;
r=min(r,n);
int idl=(l-1)/block,idr=(r-1)/block;
if(idl==idr)
{
c[l]+=k;
if(r<min((int)R[idl],n)) c[r+1]-=k;
sum[idl]+=(r-l+1)*k;
}
else
{
c[l]+=k;
sum[idl]+=(R[idl]-l+1)*k;
for(int i=idl+1;i<idr;i++)
{
pub[i]+=k;
sum[i]+=k*block;
}
c[L[idr]]+=k;
sum[idr]+=(r-(L[idr])+1)*k;
if(r<min((int)R[idr],n)) c[r+1]-=k;
}
}
}
}
}