5 条题解
-
3
一道线段树入门题。上代码:
namespace solver11 { struct SegTree { int l,r; long long val,tag; }t[50]; inline void Push_Up(int id) { t[id].val=t[id<<1].val+t[id<<1|1].val; } inline void Push_Down(int id) { if (t[id].tag) { int mid=(t[id].l+t[id].r)>>1; t[id<<1].tag+=t[id].tag; t[id<<1|1].tag+=t[id].tag; t[id<<1].val+=(mid-t[id].l+1)*t[id].tag; t[id<<1|1].val+=(t[id].r-mid)*t[id].tag; t[id].tag=0; } } inline void Build(int id,int l,int r) { t[id].l=l; t[id].r=r; if (l==r) return; int mid=(l+r)>>1; Build(id<<1,l,mid); Build(id<<1|1,mid+1,r); Push_Up(id); } inline void Change(int id,int l,int r,int val) { if (l<=t[id].l && t[id].r<=r) { t[id].tag+=val; t[id].val+=val*(t[id].r-t[id].l+1); return; } Push_Down(id); int mid=(t[id].l+t[id].r)>>1; if (r<=mid) Change(id<<1,l,r,val); else if (l>mid) Change(id<<1|1,l,r,val); else { Change(id<<1,l,mid,val); Change(id<<1|1,mid+1,r,val); } Push_Up(id); } inline long long Query(int id,int l,int r) { if (l<=t[id].l && t[id].r<=r) return t[id].val; Push_Down(id); int mid=(t[id].l+t[id].r)>>1; if (r<=mid) return Query(id<<1,l,r); else if (l>mid) return Query(id<<1|1,l,r); else return Query(id<<1,l,mid)+Query(id<<1|1,mid+1,r); } inline void solve() { Build(1,1,2); Change(1,1,1,read()); Change(1,2,2,read()); cout << Query(1,1,2) << endl; } }
信息
- ID
- 550
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- (无)
- 递交数
- 911
- 已通过
- 602
- 上传者