@[缪凌锴_Mathew](/user/372409) 奥对好像是这样的,光看TLE了没看这个谢谢谢谢
by YONEX @ 2024-09-20 21:26:39
@[wjr_jok](/user/1236806) @[添哥](/user/264463) @[缪凌锴_Mathew](/user/372409) 一关
by YONEX @ 2024-09-20 21:28:19
额哥们你没调用 `build`
by 缪凌锴_Mathew @ 2024-09-20 21:35:49
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll k[500005];int m,n,p;ll a,b,c,ans=0;
int add[500007],pos[500007]/*判断点属于哪一个块*/;
ll sum[500007];
int line_l[500007],line_r[500007];
inline long long read()
{
char cc=getchar();long long f=1,ans=0;
while(cc<'0' or cc>'9'){if(cc=='-')f=-1;cc=getchar();}
while(cc>='0' and cc<='9'){ans=(ans*10)+(cc-'0');cc=getchar();}
return f*ans;
}
inline void reads(){n=read();m=read();for(int i=1;i<=n;i++)k[i]=read();}
inline void build()
{
int t=sqrt(n);//块的个数
for(int i=1;i<=t;i++){line_l[i]=(i-1)*t+1;line_r[i]=i*t;}//设置左右边界
if(line_r[t]<=n){t++;line_l[t]=line_r[t-1]+1;line_r[t]=n;}//特判最后一个块不完整
for(int i=1;i<=t;i++)//初始化区间加值和这个点属于那个块
for(int j=line_l[i];j<=line_r[i];j++){pos[j]=i;sum[i]+=k[j];}
}
inline void change_point(){a=read();b=read();k[a]+=b;sum[pos[a]]+=b;}
inline void change_line()
{
a=read();b=read();
if(pos[a]==pos[b]){for(int i=a;i<=b;i++)ans+=k[i];printf("%lld\n",ans);return ;}
for(int i=pos[a]+1;i<=pos[b]-1;i++)ans+=sum[i];
for(int i=a;i<=line_r[pos[a]];i++)ans+=k[i];for(int i=line_l[pos[b]];i<=b;i++)ans+=k[i];
printf("%lld\n",ans);return ;
}
inline void main_d()
{reads();build();for(int i=1;i<=m;i++){ans=0;p=read();if(p==1){change_point();continue;}change_line();}}
int main()
{
main_d();
return 0;
}
```
@[YONEX](/user/737219) 过了
by 缪凌锴_Mathew @ 2024-09-20 21:45:47
@[缪凌锴_Mathew](/user/372409) 谢谢谢谢谢谢谢谢
by YONEX @ 2024-09-20 21:47:09
我想起了这张一年之前的图
![](https://cdn.luogu.com.cn/upload/image_hosting/1ndxojst.png)
现在改改还能用(
by Milthm @ 2024-09-20 21:47:29
@[YONEX](/user/737219) 还得是洛谷爆破,硬控我十分钟
by wjr_jok @ 2024-09-20 21:48:13
@[YONEX](/user/737219) wc你这个怎么这么快
by wjr_jok @ 2024-09-20 21:49:52
@[wjr_jok](/user/1236806) 他加了快读,输入量 $5\times10^5$,当然比你 `cin` 快
by 缪凌锴_Mathew @ 2024-09-20 21:51:29
@[缪凌锴_Mathew](/user/372409) bushi,比有些树状数组都快
by wjr_jok @ 2024-09-20 21:52:03