描述 Description
N 个气球排成一排，从左到右依次编号为 1,2,3….N. 每次给定 2 个整数 a b(a <= b),lele 便为骑上他的 “小飞鸽” 牌电动车从气球 a 开始到气球 b 依次给每个气球涂一次颜色。但是 N 次以后 lele 已经忘记了第 I 个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
输入格式 InputFormat
每个测试实例第一行为一个整数 N,(N <= 100000). 接下来的 N 行，每行包括 2 个整数 a b(1 <= a <= b <= N)。
当 N = 0，输入结束。
输出格式 OutputFormat
每个测试实例输出一行，包括 N 个整数，第 I 个数代表第 I 个气球总共被涂色的次数。
样例输入 SampleInput
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
样例输出 SampleOutput
1 1 1
3 2 1
代码 Code
差分序列 + 树状数组。区间修改，单点求值。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=100005;
int i,j,t,n,m,l,r,k,z,y,x;
int tree[maxn];
inline int lowbit(int s)
{
return s&(-s);
}
inline void ins(int s,int x)
{
while (s<=n)
{
tree[s]+=x;
s+=lowbit(s);
}
}
inline int sum(int s)
{
int t=0;
while (s>0)
{
t+=tree[s];
s-=lowbit(s);
}
return t;
}
int main()
{
while (scanf("%d",&n))
{
if (n==0) break;
memset(tree,0,sizeof(tree));
for (i=1;i<=n;i++) scanf("%d%d",&x,&y),ins(x,1),ins(y+1,-1);
for (i=1;i<n;i++) printf("%d",sum(i));
printf("%d\n",sum(n));
}
return 0;
}