树状数组模板--Color the ball

Color the ball

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个气球总共被涂色的次数。

Sample Input

Sample Output

1 1 1
3 2 1

思路不难，就是线段树||差分数组||普通树状数组||树状数组+差分的模板题

每次更新时区间各点+1，最后输出每个元素的值，总结来说就是区间更新+单点查询

TLE版本，单点修改，肯定超时，因为需要每次遍历左端点到右端点去更新，无法保持O(logn)的时间复杂度

普通正解：update数组表示从1到x每个数更新的次数，所以我们只需要update(L-1,-1)和update(R,1)表示[L,R]被更新的次数，相当于将[1,L-1]这个区间-1，再将[1,R]+1

差分+树状数组：在普通正解基础上，在每次修改区间时，利用差分数组的性质，只更新左端点L和R+1的位置

TLE：

 #include<iostream>
 #include<cstring>
 #include<math.h>
 #include<stdlib.h>
 #include<cstring>
 #include<cstdio>
 #include<utility>
 #include<algorithm>
 #include<map>
 #define lowbit(i) ((i)&(-i))
 using namespace std;
 typedef long long ll;
 inline int read(){
     ,w=;;
     while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
     )+(X<<)+(ch^),ch=getchar();
     return w?-X:X;
 }
 /*------------------------------------------------------------------------*/
 ;
 ll c[maxn];//树状数组
 int n;
 void update(int x,int v){
     for(int i=x;i<=n;i+=lowbit(i)){
         c[i]+=v;
     }
 }
 ll getsum(int x){//前x个整数之和
     ll sum=;
     ;i-=lowbit(i)){
         sum+=c[i];
     }
     return sum;
 }
 ll query(int l,int r){
     );
 }
 int main( )
 {
     ios_base::sync_with_stdio(); cin.tie(); cout.tie();
     //freopen("a.txt","r",stdin);
     //freopen("a.txt","w",stdout);

     while(cin>>n){
         )break;
         memset(c,,sizeof(c));

         int l,r;
         ;i<=;++i){

             cin>>l>>r;
             for(int j=l;j<=r;++j){
                 update(j,);
             }

         }

         ;i<=n;++i){
             cout<<query(i,i)<<" ";
         }
         cout<<endl;
     }
     ;
 }

正解：

 #include<iostream>
 #include<cstring>
 #include<math.h>
 #include<stdlib.h>
 #include<cstring>
 #include<cstdio>
 #include<utility>
 #include<algorithm>
 #include<map>
 #define lowbit(i) ((i)&(-i))
 using namespace std;
 typedef long long ll;
 inline int read(){
     ,w=;;
     while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
     )+(X<<)+(ch^),ch=getchar();
     return w?-X:X;
 }
 /*------------------------------------------------------------------------*/
 ;
 ll c[maxn];//树状数组
 int n;
 void update(int x,int v){
     ;i-=lowbit(i)){
         c[i]+=v;
     }
 }
 ll getsum(int x){//求第i个整数的值
     ll sum=;
     for(int i=x;i<=n;i+=lowbit(i)){
         sum+=c[i];
     }
     return sum;
 }
 ll query(int l,int r){
     );
 }
 int main( )
 {
     ios_base::sync_with_stdio(); cin.tie(); cout.tie();
     //freopen("a.txt","r",stdin);
     //freopen("a.txt","w",stdout);

     while(cin>>n){
         )break;
         memset(c,,sizeof(c));

         int l,r;
         ;i<=n;++i){

             cin>>l>>r;

             update(r,);
             update(l-,-);

         }

         ;i<n;++i){
             cout<<getsum(i)<<" ";
         }
         cout<<getsum(n)<<endl;
     }
     ;
 }

差分+树状数组

 #include<iostream>
 #include<cstring>
 #include<math.h>
 #include<stdlib.h>
 #include<cstring>
 #include<cstdio>
 #include<utility>
 #include<algorithm>
 #include<map>
 #define lowbit(i) ((i)&(-i))
 using namespace std;
 typedef long long ll;
 inline int read(){
     ,w=;;
     while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
     )+(X<<)+(ch^),ch=getchar();
     return w?-X:X;
 }
 /*------------------------------------------------------------------------*/
 ;
 ll c[maxn];//树状数组
 int n;
 void update(int x,int v){
     for(int i=x;i<=n;i+=lowbit(i)){
         c[i]+=v;
     }
 }
 ll getsum(int x){
     ll sum=;
     ;i-=lowbit(i)){//前x个整数之和
         sum+=c[i];
     }
     return sum;
 }
 ll query(int l,int r){
     );
 }
 int main( )
 {
     ios_base::sync_with_stdio(); cin.tie(); cout.tie();
     //freopen("a.txt","r",stdin);
     //freopen("a.txt","w",stdout);

     while(cin>>n){
         )break;
         memset(c,,sizeof(c));

         int l,r;
         ;i<=n;++i){

             cin>>l>>r;

             //update(r,1);
             //update(l-1,-1);
             update(l,);
             update(r+,-);

         }
         /*
         差分数组的性质：差分数组的前x个数的和就是x的值
         */
         ;i<n;++i){
             cout<<getsum(i)<<" ";
         }
         cout<<getsum(n)<<endl;
     }
     ;
 }

巴特西

树状数组模板--Color the ball

Color the ball

TLE：

正解：

差分+树状数组

最新文章

热门文章