@[protractor](/user/964822) 哥你这样不超时吗
by 大眼仔Happy @ 2024-02-17 11:36:27
```cpp
#include<iostream>
#define lowbit(x) (x&(-x))
#define cha(x,y) (qzh(y)-qzh(x-1))
using namespace std;
int sz[500050];
int a[500050];
int n,m,k,l,b;
void gai(int i,int x)
{
a[i]+=x;
while(i<=n)
{
sz[i]+=x;
i+=lowbit(i);
}
}
int qzh(int x)
{
int ans=0;
while(x)
{
ans+=sz[x];
x-=lowbit(x);
}
return ans;
}
int main()
{
//freopen("P4513_2.in","r",stdin);
//freopen("P4513.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>l;
gai(i,l);
}
//for(int i=1;i<=n;i++)
// cout<<sz[i]<<' ';
//cout<<'\n';
//for(int i=1;i<=n;i++)
// cout<<qzh(i)<<' ';
//cout<<'\n';
for(int i=1;i<=m;i++)
{
cin>>k>>l>>b;
if(k-1) gai(l,b-a[i]);
else
{
if(l>b) {int z=l;l=b,b=z;}
int minn=500000001;
int maxx=-500000001;
for(int i=l;i<=b;i++)
{
minn=min(qzh(i-1),minn);
maxx=max(qzh(i)-minn,maxx);
}
cout<<maxx<<'\n';
}
}
return 0;
}
```
by _ikun_newperson @ 2024-02-17 11:37:02
- 1. 你超时了，树状数组过不了，得用线段树
- 2. 记得开 $4*5*10^{5}$ ,不然会 re
by _ikun_newperson @ 2024-02-17 11:42:03
啊啊啊（线段树不会）
谢谢各位dalao，学线段树去了T_T
by protractor @ 2024-02-17 12:10:03
对了WA是怎么回事
@[_ikun_newperson](/user/788434) @[大眼仔Happy](/user/537046)
by protractor @ 2024-02-17 12:11:01