fzu 2171 线段树 lazy标记

#include<iostream>
#include<stdio.h>
#include<string.h>
#define maxx 100002
using namespace std;

struct node{int l,r,color,sum;}tree[maxx*4];

void build(int left,int right,int k)
{
    tree[k].l=left;
    tree[k].r=right;
    tree[k].color=0;
    if(left==right)
    {
        scanf("%d",&tree[k].sum);
        return;
    }
    int m;
    m=(left+right)/2;
    build(left,m,k*2);
    build(m+1,right,k*2+1);
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
}

void pushdown(int k)
{
    tree[k*2].sum-=(tree[k*2].r-tree[k*2].l+1)*tree[k].color;
    tree[k*2+1].sum-=(tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].color;
    tree[k*2].color+=tree[k].color;
    tree[k*2+1].color+=tree[k].color;
}

int sum(int left,int right,int k)
{
    if(tree[k].l==left&&tree[k].r==right)
        return tree[k].sum;
    if(tree[k].color)
    {
        pushdown(k);
        tree[k].color = 0;
    }
    int m;
    m=(tree[k].l+tree[k].r)/2;
    if(right<=m)
        return sum(left,right,k*2);
    if(left>=m+1)
        return sum(left,right,k*2+1);
    return sum(left,m,k*2)+sum(m+1,right,k*2+1);
}

void update(int left,int right,int k)
{
    if(tree[k].l==left&&tree[k].r==right)
    {
        tree[k].sum-=tree[k].r-tree[k].l+1;
        tree[k].color++;
        return ;
    }
    int m;
    m=(tree[k].l+tree[k].r)/2;
    if(right<=m)
        update(left,right,k*2);
    else if(left>=m+1)
        update(left,right,k*2+1);
    else
    {
        update(left,m,k*2);
        update(m+1,right,k*2+1);

    }tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
}



int main()
{
    int i,j,n,m,t,q,a,b;
    while(~scanf("%d%d%d",&n,&m,&q))
    {
        build(1,n,1);
        while(q--)
        {
            //printf("1");
            scanf("%d",&a); //printf(" er ");
            b=a+m-1;
            printf("%d\n",sum(a,b,1));//printf("sdfd");
            update(a,b,1);//printf("okok");
        }
    }
}