Yang818 @ 2023-10-20 19:13:24
#include<bits/stdc++.h>
#define F(_b,_e) for(int i=_b;i<=_e;i++)
#define int long long
using namespace std;
inline int read(){
int f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return f*x;
}
void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const int MAXN=2e5+5;
struct Seg_tree{
int l,r;
long long val,tag;
}t[MAXN<<2];
int a[MAXN],n,m;
void build(int pos,int left,int right){
t[pos].l=left;
t[pos].r=right;
if(left==right){
t[pos].val=a[left];
return;
}
int mid=(left+right)/2;
build(pos*2,left,mid);
build(pos*2+1,mid+1,right);
}
void spread_down(int pos){
t[pos*2].tag=t[pos].tag;
t[pos*2+1].tag=t[pos].tag;
t[pos*2].val+=(t[pos*2].r-t[pos*2+1].l+1)*t[pos].tag;
t[pos*2+1].val+=(t[pos*2+1].r-t[pos*2+1].l+1)*t[pos].tag;
t[pos].tag=0;
}
void modify(int pos,int left,int right,int delta){
if(t[pos].l>=left && t[pos].r<=right){
t[pos].val+=delta*(t[pos].r-t[pos].l+1);
t[pos].tag+=delta;
return;
}
int mid=(t[pos].l+t[pos].r)/2;
if(left<=mid) modify(pos*2,left,right,delta);
if(right>mid) modify(pos*2+1,left,right,delta);
t[pos].val=t[pos*2].val+t[pos*2+1].val;
return;
}
int query(int pos,int left,int right){
long long ans=0;
if(t[pos].l>=left&&t[pos].r<=right)
return t[pos].val;
int mid=(t[pos].l+t[pos].r)/2;
if(left<=mid)
ans+=query(pos*2,left,right);
if(right>mid)
ans+=query(pos*2+1,left,right);
return ans;
}
signed main(){
//ios::sync_with_stdio(0);
n=read();
m=read();
while(m--){
int op=read();
if(op==1){
int l=read();
int r=read();
int d=read();
modify(1,l,r,d);
}
if(op==2){
int l=read();
int r=read();
cout<<query(1,l,r)<<endl;
}
}
return 0;
}
by 半只蒟蒻 @ 2023-10-20 19:20:54
build 函数里面也要 pushup (即用两个儿子节点的信息更新父亲节点的信息)
对应的就是你代码里面的这行:
t[pos].val=t[pos*2].val+t[pos*2+1].val;
by Nobelium_255 @ 2023-10-20 19:21:17
你查询没有下传懒标记
by 半只蒟蒻 @ 2023-10-20 19:21:32
@jeffstart lz 是八倍空间啊,没问题
by 半只蒟蒻 @ 2023-10-20 19:22:14
@Nobelium_255 可能modify的时候也得推标记?我不确定
by Nobelium_255 @ 2023-10-20 19:22:47
哦,收回上句话。应该是你完全没有下传过懒标记
by Nobelium_255 @ 2023-10-20 19:23:24
@半只蒟蒻 都得推,我刚刚没看见
by 半只蒟蒻 @ 2023-10-20 19:23:42
而且这个标记下推感觉写的怪怪的
t[pos*2].val+=(t[pos*2].r-t[pos*2+1].l+1)*t[pos].tag;
应为
t[pos*2].val+=(t[pos*2].r-t[pos*2].l+1)*t[pos].tag;
by Nobelium_255 @ 2023-10-20 19:24:57
@半只蒟蒻 只能说乍一看好像挺正常,细细看全是问题
by 半只蒟蒻 @ 2023-10-20 19:26:00
而且可能区间修改的参数 d
也得开成 long long
类型的,毕竟题目没有明确说明
by 半只蒟蒻 @ 2023-10-20 19:26:48
@半只蒟蒻 query
函数的返回类型改成 long long