Color the ball
N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
题意很简单，每次都有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");
}
}
不出所料，是超时的，所以不得不做的是分析浪费时间的原因和相应的解决方案。
遍历输出的方面是不能改的，因为每一次遍历都需要输出一位数，那么浪费时间的主要步骤就是累加了，既然不能从a到b逐个加，那么就应该找一个方法尽量使该加法得到最简化。
真的是非常巧妙的运用，在做题时如果想不到可以直接使用线段树，但是代码不会如此精简。
首先我们以数组A的每一个结点来代替一个气球被染色的次数：
这样，只在起始位置加上一个单位，那么如果要输出的是第五个气球，除了第三个以外都是零，那么就是1了，需要注意的是，每次染色都是在一个范围 内的，为了避免之后的气球在累加的时候也会数目增多，如图，假设染色范围是（3，6），那么，只需要在6+1个气球处减1即可：
不妨多举几个例子验证一下，把前n项求和，得到的便是第n个气球的染色次数。
#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;
}
