Color the ball HDU1556

这题整整debug了两个小时

不同组居然要初始化  本以为built函数里面已经初始化好了！！！！！

其他无需注意

#include<cstdio>

#include<cstring>

using namespace std;

int n,p,a,b,m,x,y,ans;

struct node

{

    int l,r,w,f;

}tree[];

inline void build(int k,int ll,int rr)//建树

{

    tree[k].l=ll,tree[k].r=rr;

    if(tree[k].l==tree[k].r)

    {

        tree[k].w=;

        return;

    }

    int m=(ll+rr)/;

    build(k*,ll,m);

    build(k*+,m+,rr);

    tree[k].w=tree[k*].w+tree[k*+].w;

}

inline void down(int k)//标记下传

{

    tree[k*].f+=tree[k].f;

    tree[k*+].f+=tree[k].f;

    tree[k*].w+=tree[k].f*(tree[k*].r-tree[k*].l+);

    tree[k*+].w+=tree[k].f*(tree[k*+].r-tree[k*+].l+);

    tree[k].f=;

}

inline void ask_point(int k)//单点查询

{

    if(tree[k].l==tree[k].r)

    {

        ans=tree[k].w;

        return ;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/;

    if(x<=m) ask_point(k*);

    else ask_point(k*+);

}

inline void change_interval(int k)//区间修改

{

    if(tree[k].l>=a&&tree[k].r<=b)

    {

        tree[k].w+=(tree[k].r-tree[k].l+)*y;

        tree[k].f+=y;

        return;

    }

    if(tree[k].f) down(k);

    int m=(tree[k].l+tree[k].r)/;

    if(a<=m) change_interval(k*);

    if(b>m) change_interval(k*+);

    tree[k].w=tree[k*].w+tree[k*+].w;

}

int main()

{

   while(scanf("%d",&n)==&&n)

   {

       memset(tree,,sizeof(tree));

       build(,,n);

        y=;

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

       {

           scanf("%d%d",&a,&b);

           change_interval();

       }

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

       {

           ans=;

           ask_point();

           printf("%d ",ans);

       }

       ans=;

       ask_point();

       printf("%d\n",ans);

   }

   return ;

}

可以用树状数组来做

普通的树状数组是改单点 求区间 或者改单点 求单点（做差）

但是树状数组也可以改区间 求单点 sum即为单点

每次更新为    参数~n  均+=val

#include <cstdio>

#include <cstring>

const int maxn = ;

int c[maxn],n;

int Lowbit(int x)

{

    return x&(-x);

}

void update(int k,int x)

{

    while(k <= n)

    {

        c[k] += x;

        k += Lowbit(k);

    }

}

int getsum(int x)

{

    int sum = ;

    while(x > )

    {

        sum += c[x];

        x -= Lowbit(x);

    }

    return sum;

}

int main()

{

    int a,b;

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

    {

        memset(c,,sizeof(c));

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

        {

            scanf("%d%d",&a,&b);

            update(a,);

            update(b+,-);

        }

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

            printf("%d ",getsum(i));

        printf("%d\n",getsum(n));

    }

    return ;

}