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

题意：容易理解。

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

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

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

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

struct node{

    int l , r;

    int sum;

    int color;

}tree[*];

int n,len,a[];

void buildTree(int l,int r,int n)

{

    int mid = (l + r) >> ;

    tree[n].l = l;

    tree[n].r = r;

    tree[n].color = ;

    if(l == r)

    {

        tree[n].sum = a[l];

        return ;

    }

    buildTree(l,mid,n*);

    buildTree(mid+,r,n*+);

    tree[n].sum = tree[n*].sum + tree[n*+].sum;

}

void pushDown(int n)

{

    tree[n*].sum = tree[n*].sum - (tree[n*].r - tree[n*].l + ) * tree[n].color;

    tree[n*+].sum = tree[n*+].sum - (tree[n*+].r - tree[n*+].l + ) * tree[n].color;

    tree[n*].color += tree[n].color;

    tree[n*+].color += tree[n].color;

}

int calSum(int x,int y,int n)

{

    int mid = (tree[n].l + tree[n].r) >> ;

    if(tree[n].l==x && tree[n].r == y)

        return tree[n].sum;

    if(tree[n].color)

    {

        pushDown(n);

        tree[n].color = ;

    }

    if(y <= mid)

        return calSum(x , y , n*);

    else if(x>mid)

        return calSum(x , y , n*+);

    else

        return calSum(x , mid , n*) + calSum(mid+ , y , n*+);

}

void update(int x , int y , int n)

{

    int mid = (tree[n].l + tree[n].r) >> ;

    if(tree[n].l == x && tree[n].r == y)

    {

        tree[n].sum = tree[n].sum - (tree[n].r - tree[n].l + );

        tree[n].color ++;

        return ;

    }

    if(y <= mid)

        update(x , y , n*);

    else if(x > mid)

        update(x , y , n*+);

    else

    {

        update(x , mid , n*);

        update(mid+ , y , n*+);

    }

    tree[n].sum = tree[n*].sum + tree[n* + ].sum;

}

int main()

{

    int i,q,x;

    while(scanf("%d%d%d",&n,&len,&q)!=EOF)

    {

        for(i=;i<=n;i++)

            scanf("%d",&a[i]);

        buildTree(,n,);

        while(q--)

        {

            scanf("%d",&x);

            printf("%d\n",calSum(x , x+len- , ));

            update(x , x+len- , );

        }

    }

    return ;

}

巴特西

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

最新文章

热门文章