Color the ball
N個氣球排成一排科乎，從左到右依次編號為1,2,3....N.每次給定2個整數(shù)a b(a <= b),lele便為騎上他的“小飛鴿"牌電動車從氣球a開始到氣球b依次給每個氣球涂一次顏色。但是N次以后lele已經(jīng)忘記了第I個氣球已經(jīng)涂過幾次顏色了菌瘫，你能幫他算出每個氣球被涂過幾次顏色嗎？
題意很簡單慎颗，每次都有a到b的氣球加一蟋座，所以很快就寫出了代碼：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#define MMAX 100005
using namespace std;
int C[MMAX];
void main()
{
int i,j,n,m,k,l;
while(scanf("%d",&n)&&n!=0)
{
memset(C,0,sizeof (C));
for (i=0;i<n;i++)
{
scanf("%d%d",&k,&l);
for(j=k;j<=l;j++)
C[j]++;
}
for (i=1;i<=n;i++)
{
printf("%d",C[i]);
if (i!=n)
printf(" ");
}
printf("\n");
}
}
不出所料，是超時的会钝，所以不得不做的是分析浪費時間的原因和相應(yīng)的解決方案。
遍歷輸出的方面是不能改的工三，因為每一次遍歷都需要輸出一位數(shù)顽素，那么浪費時間的主要步驟就是累加了，既然不能從a到b逐個加徒蟆，那么就應(yīng)該找一個方法盡量使該加法得到最簡化胁出。
真的是非常巧妙的運用，在做題時如果想不到可以直接使用線段樹段审，但是代碼不會如此精簡全蝶。
首先我們以數(shù)組A的每一個結(jié)點來代替一個氣球被染色的次數(shù)：
這樣始苇，只在起始位置加上一個單位，那么如果要輸出的是第五個氣球筐喳，除了第三個以外都是零催式，那么就是1了，需要注意的是避归，每次染色都是在一個范圍 內(nèi)的荣月，為了避免之后的氣球在累加的時候也會數(shù)目增多，如圖梳毙，假設(shè)染色范圍是（3哺窄，6），那么账锹，只需要在6+1個氣球處減1即可：
不妨多舉幾個例子驗證一下萌业，把前n項求和，得到的便是第n個氣球的染色次數(shù)奸柬。
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int c[100010];
int n;
int lowbit(int x){
return x&-x;
}
void modify(int pos,int val){
while(pos<=n){//n-->b;
c[pos]+=val;
pos+=lowbit(pos);
}
}
int getr(int pos){
int sum=0;
while(pos>0){
sum+=c[pos];
pos-=lowbit(pos);
}
return sum;
}
int main(){
int a,b,i;
while(cin>>n,n){
memset(c,0, sizeof(c));
for(i=0;i<n;i++){
scanf("%d%d",&a,&b);
modify(a,1);
modify(b+1, -1);
}
for( i=1;i<=n;i++){
printf("%d%c",getr(i)," \n"[i==n]);
}
}
return 0;
}
