200 条题解

  • -1
    @ 2025-7-9 21:44:44

    这是一道非常水的线段树题目,我们可以建立一个大小为 33ww 数组,w0w_0 不用管,w1w_1aa 的值,w2w_2 暂时先存 00(因为在后来的更新函数把 222\sim2 的范围改为 bb,相当于给 0+b0+b),建树(范围 121\sim2),更新(范围 222\sim2),最后输出查询 121\sim2 范围的和。

    #include<bits/stdc++.h>
    #define lc p<<1
    #define rc p<<1|1
    using namespace std;
    struct node{
        int l,r,sum,add;
    }tr[3*4+5];
    int w[3];
    void pushup(int p){
        tr[p].sum=tr[lc].sum+tr[rc].sum;
    }
    void pushdown(int p){
        if(tr[p].add){
            tr[lc].sum+=(tr[lc].r-tr[lc].l+1)*tr[p].add;
            tr[rc].sum+=(tr[rc].r-tr[rc].l+1)*tr[p].add;
            tr[lc].add+=tr[p].add;
            tr[rc].add+=tr[p].add;
            tr[p].add=0;
        }
    }
    void build(int p,int l,int r){
        tr[p]={l,r,w[l],0};
        if(l==r)return ;
        int mid=l+r>>1;
        build(lc,1,mid);
        build(rc,mid+1,r);
        pushup(p);
    }
    void update(int p,int l,int r,int k){
        if(l<=tr[p].l&&tr[p].r<=r){
            tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
            tr[p].add+=k;
            return ;
        }
        int mid=tr[p].l+tr[p].r>>1;
        pushdown(p);
        if(l<=mid)update(lc,l,r,k);
        if(r>mid)update(rc,l,r,k);
        pushup(p);
    }
    int query(int p,int l,int r){
        if(l<=tr[p].l&&tr[p].r<=r)return tr[p].sum;
        int mid=tr[p].l+tr[p].r>>1;
        pushdown(p);
        int sum=0;
        if(l<=mid)sum+=query(lc,l,r);
        if(r>mid)sum+=query(rc,l,r);
        return sum;
    }
    int main(){
        cin>>w[1];
        w[2]=0;
        build(1,1,2);
        int b;
        cin>>b;
        update(1,2,2,b);
        cout<<query(1,1,2);
        return 0;
    }
    

    信息

    ID
    56
    时间
    1000ms
    内存
    1024MiB
    难度
    1
    标签
    递交数
    12363
    已通过
    5577
    上传者