@[chenbinggang](/user/141331)
瞟了一眼,数组开小了
线段树至少开4倍空间
by Gokix @ 2021-06-18 22:07:32
@[Dаrk_night](/user/191748) orz
by Meaninglessness @ 2021-06-18 22:08:50
@[Dаrk_night](/user/191748) 没少参数,用的是#define
by tribool4_in @ 2021-06-18 22:10:27
@[chenbinggang](/user/141331) 就是数组开小了,要开4倍
by tribool4_in @ 2021-06-18 22:12:06
@[wangwls](/user/341650) 对不起,wssb
by Rosaya @ 2021-06-18 22:12:20
建议去学 2 倍空间的线段树写法,而且不要滥用 `#define`。
by ud2_ @ 2021-06-18 22:16:45
@[sjx233_](/user/206953) 这咋就滥用 define 了 /jk
by syksykCCC @ 2021-06-18 22:19:25
请原谅我刚刚的无知,我很抱歉。
楼主的错误大概有几个:
1.要开long long,范围说的和在long long内,可能会爆int
2.
区间的长度应该是:
```
(min(R,r)-max(L,l)+1);
```
3.如果在前面会把标记使用,那么在直接包含的区间里就不应该再算标记,要不然会多加。
代码(亲测可过):
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define lson l,mid,k<<1
#define rson mid+1,r,k<<1|1
#define int long long
int c[500000],add[500000],sum[500000];
int n,m;
void Push(int k)
{
c[k]=c[k<<1]+c[k<<1|1];
return;
}
void build(int l,int r,int k)
{
if(l==r)
{
scanf("%lld",&c[k]);
return;
}
int mid=l+r>>1;
build(lson);
build(rson);
Push(k);
}
void modify(int L,int R,int C,int l,int r,int k)
{
c[k]+=C*(min(R,r)-max(L,l)+1);
if(L<=l&&R>=r)
{
add[k]+=C;
return;
}
// cout<<c[k]<<" "<<k<<endl;
int mid=l+r>>1;
if(L<=mid) modify(L,R,C,lson);
if(R>mid)modify(L,R,C,rson);
// else modify(L,R,C,lson),modify(L,R,C,rson);
}
int query(int L,int R,int l,int r,int k)
{
if(L<=l&&R>=r)return c[k];
int mid=(l+r)>>1;
int res=add[k]*(min(R,r)-max(L,l)+1);
if(L<=mid) res+=query(L,R,lson);
if(R>mid) res+=query(L,R,rson);
return res;
}
signed main()
{
scanf("%lld%lld",&n,&m);
build(1,n,1);
int t,x,y,z;
for(int i=1;i<=m;i++)
{
scanf("%lld",&t);
if(t==1)
{
//cout<<100;
scanf("%lld%lld%lld",&x,&y,&z);
modify(x,y,z,1,n,1);
}
if(t==2)
{
scanf("%lld%lld",&x,&y);
// res=0;
cout<<query(x,y,1,n,1)<<endl;
}
}
}
```
by Rosaya @ 2021-06-18 22:23:24
但是说句闲话,您不是五天前刚AC过吗(
by Rosaya @ 2021-06-18 22:27:40
@[Dаrk_night](/user/191748) 谢谢大佬
我这题想用标记下传和标记永久化都试一遍
by chenbinggang @ 2021-06-19 12:46:20