首页 > 代码库 > Color the ball

Color the ball

2024-07-13 10:33:28   216人阅读

hdu1556:http://acm.hdu.edu.cn/showproblem.php?pid=1556

题意：中文题。

题解：这一题当然可以直接用线段树来打，但是最近在学树状数组，所以用树状数组打了。树状数组有两种更新和求和的方式。1是向上更新，向下查询。2是向下更新，向上查询。第二种可以用来区间更新。例如更新(u,v,num),先update(v,num),然后update(u-1,-num);getsum(i)得到的就是第i个数的值。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define  MAXN  1000000 6 using namespace std; 7 int c[MAXN]; 8 int n,u,v;; 9 int lowbit(int x){10    return x&(-x);11 }12 void add(int x,int num){13     while(x>=1){14         c[x]+=num;15         x-=lowbit(x);16     }17 }18 int getsum(int x){19    int sum=0;20    while(x<=n){21      sum+=c[x];22      x+=lowbit(x);23    }24    return sum;25 }26 int main(){27     while(~scanf("%d",&n)&&n){28       memset(c,0,sizeof(c));29       for(int i=1;i<=n;i++){30         scanf("%d%d",&u,&v);31         add(v,1);32         add(u-1,-1);33       }34       for(int i=1;i<n;i++)35       printf("%d ",getsum(i));36       printf("%d\n",getsum(n));37     }38 }
View Code


联系
我们