FZU 2171(线段树的延迟标记)

题意：容易理解。

分析：时隔很久，再一次写了一道线段树的代码，之前线段树的题也做了不少，包括各种延迟标记，但是在组队分任务之后，我们队的线段树就交给了另外一个队友在搞，

然后我就一直没去碰线段树的题了，但是我现在发现这种做法不是很好，导致我现在的思维受到了很大的局限性，所以我现在想纠正这种错误，该做的就应该去做，就像

高中一样不能太偏科!一道比较简单的线段树延迟标记！

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath>struct node{int l , r;int sum;int color; }tree[100005*4];int n,len,a[100005];void buildTree(int l,int r,int n) {int mid = (l + r) >> 1;tree[n].l = l;tree[n].r = r;tree[n].color = 0;if(l == r){tree[n].sum = a[l];return ;}buildTree(l,mid,n*2);buildTree(mid+1,r,n*2+1);tree[n].sum = tree[n*2].sum + tree[n*2+1].sum; }void pushDown(int n) {tree[n*2].sum = tree[n*2].sum - (tree[n*2].r - tree[n*2].l + 1) * tree[n].color;tree[n*2+1].sum = tree[n*2+1].sum - (tree[n*2+1].r - tree[n*2+1].l + 1) * tree[n].color;tree[n*2].color += tree[n].color;tree[n*2+1].color += tree[n].color; }int calSum(int x,int y,int n) {int mid = (tree[n].l + tree[n].r) >> 1;if(tree[n].l==x && tree[n].r == y)return tree[n].sum;if(tree[n].color){pushDown(n);tree[n].color = 0;}if(y <= mid)return calSum(x , y , n*2);else if(x>mid)return calSum(x , y , n*2+1);elsereturn calSum(x , mid , n*2) + calSum(mid+1 , y , n*2+1); }void update(int x , int y , int n) {int mid = (tree[n].l + tree[n].r) >> 1;if(tree[n].l == x && tree[n].r == y){tree[n].sum = tree[n].sum - (tree[n].r - tree[n].l + 1);tree[n].color ++;return ;}if(y <= mid)update(x , y , n*2);else if(x > mid)update(x , y , n*2+1);else{update(x , mid , n*2);update(mid+1 , y , n*2+1);}tree[n].sum = tree[n*2].sum + tree[n*2 + 1].sum; }int main() {int i,q,x;while(scanf("%d%d%d",&n,&len,&q)!=EOF){for(i=1;i<=n;i++)scanf("%d",&a[i]);buildTree(1,n,1);while(q--){scanf("%d",&x);printf("%d\n",calSum(x , x+len-1 , 1));update(x , x+len-1 , 1);}}return 0; }

 

 

转载于:https://www.cnblogs.com/jiangjing/p/3696080.html

总结

以上是生活随笔为你收集整理的FZU 2171(线段树的延迟标记)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。