@[Chase_future](/user/241817) 请问那个 `buildd` 函数是干什么用的啊，为什么没看见调用？
by hihihi198 @ 2021-09-21 11:49:54
@[Chase_future](/user/241817) 感觉这份代码极有可能是写错了导致时间复杂度不对，而不是常数问题。
by hihihi198 @ 2021-09-21 11:54:39
@[hihihi198](/user/311369) 不知道，我加了建块就wa了，不加反而能70分
by Chancylaser @ 2021-09-21 11:56:30
@[Chase_future](/user/241817) 那很可能是建块的时候或者对块处理的时候错了，然后你没有建块被卡成了暴力。
刚刚瞄到你对 `dx` 的处理好像有问题。
by hihihi198 @ 2021-09-21 11:59:58
@[hihihi198](/user/311369) 有啥问题呀大佬能帮我看看咩
by Chancylaser @ 2021-09-21 12:02:06
刚刚编译查到 `printf` 输出了 `%d`。我先改了。
by hihihi198 @ 2021-09-21 12:04:27
@[Chase_future](/user/241817) 天哪原来您样例都没过。
您这个分块的思路完全乱了啊。每个块应该记录一个 tag 啊。
by hihihi198 @ 2021-09-21 12:18:31
@[hihihi198](/user/311369) tag指？
现在我调好了/kk，现在第八个数据需要跑7秒
```cpp
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
long long n,m;
const long long M = 100005;
long long dx[M];
long long l[M],r[M];
long long a[M];
long long belong[M];
long long bg,sum;
inline long long read()
{
long long x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void buildd(){
bg=sqrt(n);
sum=n/bg;
if(n%bg)
sum++;
for(int i=1;i<=sum;i++)
l[i]=(i-1)*bg+1,r[i]=i*bg;
r[sum]=n;
for(int i=1;i<=n;i++)
belong[i]=(i-1)/bg+1;
for(int i=1;i<=sum;i++)
for(int j=l[i];j<=r[i];j++)
dx[i]+=a[j];
return;
}
inline void updata(long long x,long long y,long long k){
if(belong[x]==belong[y]){
for(int i=x;i<=y;i++)
a[i]+=k;
dx[belong[x]]+=(y-x+1)*k;
}
else{
for(int i=x;i<=r[belong[x]];i++)
a[i]+=k;
dx[belong[x]]+=(r[belong[x]]-x+1)*k;
for(int i=belong[x]+1;i<=belong[y]-1;i++)
dx[i]+=(r[i]-l[i]+1)*k;
for(int i=r[belong[x]]+1;i<l[belong[y]];i++)
a[i]+=k;
for(int i=l[belong[y]];i<=y;i++)
a[i]+=k;
dx[belong[y]]+=(y-l[belong[y]]+1)*k;
}
return;
}
long long query(long long x,long long y){
long long ans=0;
if(belong[x]==belong[y]){
for(int i=x;i<=y;i++)
ans+=a[i];
return ans;
}
else{
for(int i=x;i<=r[belong[x]];i++)
ans+=a[i];
for(int i=belong[x]+1;i<=belong[y]-1;i++)
ans+=dx[i];
for(int i=l[belong[y]];i<=y;i++)
ans+=a[i];
return ans;
}
return ans;
}
int main(){
//freopen("P3372_8.in","r",stdin);
//freopen("P3372_8.out","w",stdout);
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
buildd();
long long qqq;
for(int i=1;i<=m;i++){
qqq=read();
if(qqq==1){
long long x,y,k;
x=read(),y=read(),k=read();
updata(x,y,k);
/*for(int i=1;i<=sqrt(n)+1;i++)
cout<<dx[i]<<" ";
puts("");puts("");puts("");*/
}
if(qqq==2){
long long wh,jjj;
wh=read(),jjj=read();
printf("%lld\n",query(wh,jjj));
}
}
return 0;
}
```
by Chancylaser @ 2021-09-21 12:19:38
@[hihihi198](/user/311369) 个人认为updata里的
```cpp
for(int i=belong[x]+1;i<=belong[y]-1;i++)
dx[i]+=(r[i]-l[i]+1)*k;
for(int i=r[belong[x]]+1;i<l[belong[y]];i++)
a[i]+=k;
```
a[i]的更新比较慢，有啥解决方法吗
by Chancylaser @ 2021-09-21 12:21:10
@[Chase_future](/user/241817) 所以您 AC 了？
by hihihi198 @ 2021-09-21 12:22:14