2 条题解

  • 1
    @ 2026-1-11 19:03:51

    要硬说的话其实不需要关流也能过,但是懒标记一定要写对。同时注意N的范围,我第一次开小了导致RE

    #include<iostream>
    using namespace std;
    #define lc p<<1
    #define rc p<<1|1
    #define N 200005
    long long arr[N];
    
    struct node
    {
        long long l,r,sum,add;
    }tr[N*4];
    
    void PushUp(int p)
    {
        tr[p].sum=tr[lc].sum+tr[rc].sum;
    }
    
    void PushDown(long long p)
    {
        if(tr[p].add)
        {
            tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1);
            tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1);
            tr[lc].add+=tr[p].add;
            tr[rc].add+=tr[p].add;
            tr[p].add=0;
        }
    }
    
    void Update(long long p,int x,int y,long long k) //区间添加。
    {
        if(x<=tr[p].l&&tr[p].r<=y)
        {
            tr[p].sum+=k*(tr[p].r-tr[p].l+1);
            tr[p].add+=k;
            return ;
        }
        long long m=(tr[p].l+tr[p].r)>>1;
        PushDown(p);
        if(x<=m) Update(lc,x,y,k);
        if(y>m) Update(rc,x,y,k);
        PushUp(p);
    }
    
    long long Query(long long p,long long l,int r)  //查询
    {
        if(l<=tr[p].l&&tr[p].r<=r)
        {
            return tr[p].sum;
        }
        long long m=(tr[p].l+tr[p].r)>>1;
        PushDown(p);
        long long sum=0;
        if(l<=m) sum+=Query(lc,l,r);
        if(r>m) sum+=Query(rc,l,r);
        return sum;
    }
    
    void Build(long long p,long long l,long long r)
    {
        tr[p]={l,r,arr[l],0};
        if(l==r) return ;
        long long m=(l+r)>>1;
        Build(lc,l,m);
        Build(rc,m+1,r);
        PushUp(p);
    }
    
    long long n,m,op,x,y,k;
    int main()
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>arr[i];
        Build(1,1,n);
        while(m--)
        {
            cin>>op;
            switch (op)
            {
                case 1:
                    cin>>x>>y>>k;
                    Update(1,x,y,k);
                    break;
            
                case 2:
                    cin>>x;
                    long long res=Query(1,x,x);
                    cout<<res<<"\n";
                    break;
            }
        }
        return 0;
    }
    

    信息

    ID
    58
    时间
    1000ms
    内存
    256MiB
    难度
    4
    标签
    递交数
    87
    已通过
    25
    上传者