HDU 1556 Color the ball【树状数组】-白红宇

HDU 1556 Color the ball【树状数组】

阅读量：5304 次

发布时间：2019-06-14

本文共 1041 字，大约阅读时间需要 3 分钟。

题意：给出n个区间，每次给这个区间里面的数加1，询问单点的值

一维的区间更新，单点查询，还是那篇论文里面讲了的

1 #include
      
          2 #include
       
           3 #include
        
           4 #include 
         
            5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
                10 #include
               
                 11 using namespace std;12 13 typedef long long LL;14 const int INF = (1<<30)-1;15 const int mod=1000000007;16 const int maxn=100005;17 18 int n;19 int c[maxn];20 21 int lowbit(int x){ return x &(-x);}22 23 int sum(int x){24 int ret=0;25 while(x>0){26 ret+=c[x];x-=lowbit(x);27 }28 return ret;29 }30 31 void add(int x,int d){32 while(x<=n){33 c[x]+=d; x+=lowbit(x);34 }35 }36 37 int main(){38 while(scanf("%d",&n) != EOF){39 if(n == 0) break;40 memset(c,0,sizeof(c));41 for(int i=1;i<=n;i++){42 int a,b;43 scanf("%d %d",&a,&b);44 add(a,1);add(b+1,-1);45 }46 printf("%d",sum(1));47 for(int i=2;i <= n;i++)48 printf(" %d",sum(i));49 printf("\n");50 }51 return 0;52 }