csq_pig @ 2023-10-06 19:45:34
求大佬解救!!!我全都改成longlong了,怎么还是最后三个点RE呢?
//坑了我很久的一个点(搞不懂为什么),我原以为,只要在区间查询的同时下传就好了(平时就存着,只有要求和的时候再下传)
//然而神奇的是,只在区间修改、或者只在区间查询的时候下传,都不能求出正解,必须两个函数都要有下传操作,才能求出正解,这究竟是为啥呢???照理来说只要查询的时候下传就好了呀
#include <bits/stdc++.h>
using namespace std;
class T {
public:
long long l,r,lazy; //线段树lazy标记,用于修改区间后的区间和查询
long long ans;
};
long long n,m,a[100010];
T tree[400010];
void makeTree (long long i, long long l, long long r)
{
tree[i].l=l; tree[i].r=r; // i节点的线段树的区间范围
if (l==r) {
tree[i].ans=a[l];
return ;
}
long long mid=(l+r)/2;
makeTree(i*2,l,mid);
makeTree(i*2+1,mid+1,r); // 递归左右儿子
tree[i].ans=tree[i*2].ans+tree[i*2+1].ans; // 线段树区间之和
}
void treeAdd (long long i,long long l,long long r,long long k)
{
if (tree[i].lazy!=0) { // *** lazy的下传!!!lazy是线段树的关键!!! ***
tree[i*2].lazy+=tree[i].lazy;
tree[i*2].ans+=tree[i].lazy*(tree[i*2].r-tree[i*2].l+1);
tree[i*2+1].lazy+=tree[i].lazy;
tree[i*2+1].ans+=tree[i].lazy*(tree[i*2+1].r-tree[i*2+1].l+1);
tree[i].lazy=0;
}
// cout<<"i = "<<i<<endl;
if (tree[i].l>=l && tree[i].r<=r) { // 区间修改
tree[i].lazy+=k; // lazy标记
tree[i].ans+=(tree[i].r-tree[i].l+1)*k;
return ;
}
if (tree[i*2].r>=l) treeAdd(i*2,l,r,k); // 如果要修改区间与左儿子有交集
if (tree[i*2+1].l<=r) treeAdd(i*2+1,l,r,k); // 如果要修改区间与右儿子有交集
tree[i].ans=tree[i*2].ans+tree[i*2+1].ans; // 区间之和
}
long long treeAsk (long long i,long long l,long long r)
{
if (tree[i].lazy!=0) { // *** lazy的下传!!!lazy是线段树的关键!!! ***
tree[i*2].lazy+=tree[i].lazy;
tree[i*2].ans+=tree[i].lazy*(tree[i*2].r-tree[i*2].l+1);
tree[i*2+1].lazy+=tree[i].lazy;
tree[i*2+1].ans+=tree[i].lazy*(tree[i*2+1].r-tree[i*2+1].l+1);
tree[i].lazy=0;
}
// cout<<"i = "<<i<<endl;
long long sum=0;
if (tree[i].r<=r && tree[i].l>=l) { // 返回区间和
return tree[i].ans;
}
if (tree[i*2].r>=l) sum+=treeAsk(i*2,l,r); // 如果要修改区间与左儿子有交集
if (tree[i*2+1].l<=r) sum+=treeAsk(i*2+1,l,r); // 如果要修改区间与右儿子有交集
return sum;
}
int main()
{
cin>>n>>m;
for (long long i=1;i<=n;i++) scanf("%lld",&a[i]);
makeTree(1,1,n);
// for (long long i=1;i<=2*n;i++)
// cout<<tree[i].ans<<" ";
for (long long i=1;i<=m;i++) {
long long p,x,y,k;
scanf("%lld",&p);
if (p==1) {
scanf("%lld%lld%lld",&x,&y,&k);
treeAdd(1,x,y,k);
}
else {
scanf("%lld%lld",&x,&y);
cout<<treeAsk(1,x,y)<<endl;
}
// for (long long i=1;i<=2*n;i++)
// cout<<tree[i].ans<<" ";
// cout<<endl;
}
return 0;
}
by xhxissz @ 2023-10-06 19:48:26
@csq_pig 不懂就问,RE关long long 什么事
by ZhongYuLin @ 2023-10-06 20:02:01
你看一下线段树二,应该能解决你的疑惑
by zqh123b @ 2023-10-06 20:02:15
@csq_pig 一般来说,RE可能是:
by hytallenxu @ 2023-10-06 20:03:13
数组开大一点 a开200010 T开800010 就可以了
by liaiyang @ 2023-10-06 20:04:56
建树时将lazy和ans归零试试
这个线段树感觉哪都有问题,又感觉哪都没问题
by not_clever_syl @ 2023-10-06 20:08:32
懒标记线段树最好开8倍空间 不然容易寄
by csq_pig @ 2023-10-21 19:43:01
@zqh123b 感谢!!!!