B - Color the ball (差分数组,树状数组

时间:2022-03-04 21:02:08
     N个气球排成一排,从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗? 
Input
    每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行,每行包括2个整数a b(1 <= a <= b <= N)。
    当N = 0,输入结束。
Output
    每个测试实例输出一行,包括N个整数,第I个数代表第I个气球总共被涂色的次数。

 

差分数组 是 前缀和数组 的 你过程;

 

原数组就是其差分数组的前缀和数组,

即对于数组d[ i ] 的差分数组f[ i ]有: f[i]=d[i]-d[i-1];

 

差分数组可以快速处理区间加减操作:

在区间l ~ r 上加1 ,即令差分数组 f[l]++,f[r]--;

 

树状数组又可以在o(log n) 的时间复杂度内求前缀和,结合差分数组即可解决此题; 

本题是离线查询(所有操作进行完后查询),如果是在线查询还是要写线段树;

 

#include <cstdio>
#include <cstring>
#include <string.h>
using namespace std;
int t[105000];

int n;
int lowbit( int x){
     return x&( -x);
}

void add( int  i,int  v){
     while( i <= n){
         t[i] += v;
         i += lowbit( i );
     }
}

int sum( int i){
     int s = 0;
     while( i>0){
         s += t[i];
         i-= lowbit( i );
     }
     return s;
}

int main( ){
     int a ,b;
     while( ~scanf( "%d",&n) && n){
         memset( t ,0 ,sizeof(t) );
         for( int i=0 ;i<n ;i++){
             scanf( "%d%d" ,&a ,&b);
             add( a ,1);
             add( b+1 ,-1);
         }
         for( int i=1 ;i<n ;i++){
             printf("%d ",sum( i));
         }
         printf( "%d\n" ,sum(n));
     }
     return 0;
}