首页 > 代码库 > FZU_Problem 2171 防守阵地 II
FZU_Problem 2171 防守阵地 II
http://acm.fzu.edu.cn/problem.php?pid=2171
线段树模板题,成段增减,区间求和。
思路:先查询,后更新。
#include<cstdio> #define lson l , m ,rt << 1 #define rson m+1 , r , rt << 1 | 1 const int maxn = 100002; int add[maxn << 2]; int sum[maxn << 2]; void PushUP(int rt) { sum[rt]=sum[rt << 1]+sum[rt << 1 | 1]; } void PushDown(int rt,int m) { if(add[rt]) { add[rt << 1] += add[rt]; add[rt<< 1 | 1] += add[rt]; sum[rt << 1] += add[rt] * (m - (m >> 1)); sum[rt << 1 | 1] += add[rt] * (m >> 1); add[rt] = 0; } } void build(int l,int r,int rt) { add[rt] = 0; if(l==r) { scanf("%d",&sum[rt]); return; } int m=(l+r) >> 1; build(lson); build(rson); PushUP(rt); } void update(int L,int R,int c,int l,int r,int rt) { if(L <= l && r <= R) { add[rt] += c; sum[rt] += c * (r - l + 1); return; } PushDown(rt , r - l + 1); int m = (l + r) >> 1; if(L <= m) update(L , R , c , lson); if(m < R) update(L , R , c , rson); PushUP(rt); } int query(int L,int R,int l,int r,int rt) { if(L <= l && r <= R) { return sum[rt]; } PushDown(rt , r - l + 1); int m= (l+r) >> 1; int ret = 0; if(L <= m) ret+=query(L , R , lson); if(m < R) ret+=query(L , R , rson); return ret; } int main() { int n,m,q; while(~scanf("%d%d%d",&n,&m,&q)) { build(1,n,1); int ans,x; while(q--) { scanf("%d",&x); ans=query(x,x+m-1,1,n,1); update(x,x+m-1,-1,1,n,1); printf("%d\n",ans); } } return 0; }
区间更新需用到延迟标记,简单来说就算每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。