Problem Description
N个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
简单的区间修改，单点统计。
1、离散化 ； 2、树状数组； 3、线段树
1、离散化
#include <stdio.h>
#include <string.h>
#define MAXN 100000 + 5
int bit[MAXN];
int main()
{
int n, i, a, b;
while(scanf("%d",&n), n )
{
memset(bit, 0, sizeof bit );
for(i=0; i<n; ++i) {
scanf("%d%d",&a,&b);
bit[a]++;
bit[b+1]--;
}
int tot = 0;
for(i=1; i<=n; ++i) {
tot += bit[i];
printf("%d%c",tot," \n"[i==n]);
}
}
return 0;
}
2、树状数组
#include <stdio.h>
#include <string.h>
#define MAXN 100000 + 5
int c[MAXN], n;
int lowbit(int x) {return (x&-x);}
void update(int i, int d) { for(;i<=n; i+=lowbit(i)) c[i]+=d; }
int getsum(int i) { int ret=0; for(;i>0; i-=lowbit(i)) ret+=c[i]; return ret;}
int main()
{
int i, a, b;
while(scanf("%d",&n),n)
{
memset(c, 0, sizeof c );
for(i=0; i<n; ++i)
{
scanf("%d%d",&a,&b);
update(a,1);
update(b+1,-1);
}
for(i=1; i<=n; ++i) {
int ans = getsum(i);
printf("%d%c",ans," \n"[i==n]);
}
}
return 0;
}
3、线段树