200 条题解
-
-1
这是一道非常水的
线段树题目,我们可以建立一个大小为 的 数组, 不用管, 存 的值, 暂时先存 (因为在后来的更新函数把 的范围改为 ,相当于给 ),建树(范围 ),更新(范围 ),最后输出查询 范围的和。#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
- 上传者