全改成long long了,但最后3个点RE,求救!!!!!

P3372 【模板】线段树 1

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可能是:

  1. 数组开小了
  2. /0 %0

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 感谢!!!!


|