Color the ball
Time Limit: 3000msMemory Limit: 32768KB 64-bit integer IO format: %lld Java class name: Main
Submit Status PID: 1529
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
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
今天讲了树状数组，敢紧趁热写一篇。。。
因为这个东西本身原理很简单，但是如果理解的方式不对就会觉得很奇怪，所以记录一下备忘吧(:з」∠)
树状数组主要就是用来维护前缀和。
树状数组a[i]这个东西呢，维护的是一个[i－lowbit(i)+1,i]这个区间的一个和，也就是说 从i这个位置算起，向前lowbit（i），这么多这个数的和。
它的神奇之处在于，可以通过lowbit（i）来向前和向后更新它的父亲值和兄弟值。
呃。。。我的理解大概就是这样简单粗暴（和高中没差啊＝ ＝），知道它能干什么，至于为什么可以看篇http://blog.csdn.net/int64ago/article/details/7429868
比较通俗易懂一点。。
树状数组优点在于代码量小，而且能干一些线段树的事情，但处理技巧非常巧妙，一些变形很神奇。
这道题是区间修改，单点查询。
本身BIT能做的最简单的事情是单点修改，区间查询。。
这里的处理技巧是：
我们开一个数组add［i］，记录第i个点增加的值。
对于要修改的区间[l,r]，我们将add[l]+=c,add[r+1]-=c;add就是用树状数组来维护的前缀和。
这样的话，如果查询l之前的值，就是相当于对求前i个add的和，我们的修改是向后，所以不会产生影响；如果查询r之后的值，虽然更新的是向后的但是因为我们＋c又－c 所以也是不会影响的。
如果查询的值在[l,r]，因为我们BITadd 的过程是向后的（即把要更新的这个点的所有父辈节点全部更新）所以查询这之间的某一个值的时候就会把增加的这个c算进去，所以答案就会是正确的。
区间修改单点询问的话原理很好懂（呃。。还有一种方法。。我。。得回寝室了。。下次。。再写。。？）
但如果改成区间询问这个技巧就要麻烦一些了。。。
嗯，下一篇再写＝－＝
// Created by ZYD in 2015.
// Copyright (c) 2015 ZYD. All rights reserved.
//
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define Size 100000
#define ll long long
#define mk make_pair
#define pb push_back
#define mem(array) memset(array,0,sizeof(array))
typedef pair<int,int> P;
int n,l,r;
int ad[110000];
int lowbit(int k){
return k&(-k);
}
void add(int c,int k){
while(k<=n){
ad[k]+=c;
k+=lowbit (k);
}
}
int ask(int k){
int sum=0;
while(k>0){
sum+=ad[k];
k-=lowbit(k);
}
return sum;
}
int main()
{
freopen("in.txt","r",stdin);
while(~scanf("%d",&n) && n){
memset(ad,0,sizeof(ad));
for(int i=1;i<=n;i++){
scanf("%d%d",&l,&r);
add(1,l);
add(-1,r+1);
}
printf("%d",ask(1));
for(int i=2;i<=n;i++){
printf(" %d",ask(i));
}
cout<<endl;
}
return 0;
}