题目大意：

我就服中文题，多组测试实例，每组n（100000）个数，进行n次操作，每次操作为，给区间[ a , b ]（a<=b）进行一次涂色。最后问你每个点分别进行了多少次涂色。

分析：

一开始以为是区间修改的题，但是仔细一想，这个题要求的是输出每个点的涂色次数，如果用类似于线段树的那种标记下移的区间修改方法，在查询每一个点的时候，早晚还是要下移到最底层，那时间复杂度时候O(n^2)的，这就超时了。
想一下这个有一点像 POJ - 2481 Cows，只不过 POJ - 2481 Cows 查询的是区间，这次查询的是点而已。
注：少见的输出每行最后不能有空格。

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 100500

using namespace std;

int tree[maxn];
int n;
struct qu
{
    int r;int l;
}a[maxn]={0};

bool my_cmp(qu a,qu b)
{
    if(a.l==b.l)return a.r>b.r;
    return a.l<b.l; 
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x)
{
    while(x<maxn)
    {
        tree[x]++;
        x+=lowbit(x);
    }
}
int sum(int x)
{
    if(x==0)return 0;
    int s=0;
    while(x>0)
    {
        s+=tree[x];
        x-=lowbit(x);
    }
    return s;
}

int main()
{
    int num[maxn];
    while(cin>>n)
    {
        memset(tree,0,sizeof(tree));
        memset(num,0,sizeof(num));
        if(n==0)return 0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i].l>>a[i].r;
        }
        sort(a+1,a+n+1,my_cmp);
        for(int i=1;i<n;i++)
        {
            add(a[i].r);
            for(int j=a[i].l;j<a[i+1].l;j++)//确定了从num数组的 [ a[i].l , a[i+1].l )
            {
                num[j]=sum(maxn-1)-sum(j-1);
            }
        }
        add(a[n].r);
        for(int j=a[n].l;j<maxn;j++)
        {
            num[j]=sum(maxn-1)-sum(j-1);
        }
        for(int i=1;i<=n;i++)
        {
            cout<<num[i];
            if(i!=n)cout<<" ";
        }
        cout<<endl;
    }
}

后注：

幸好我之后去查了大神的解题报告，好强大的理解方法：
初始时数组A[n]为全0。当我们给区间[a,b]内的气球涂颜色的时候，我们令A[a]这个点+1，然后令A[b+1]这个点-1。然后我们令sum(x)表示x这个气球点被涂色的总次数。
比如初始时我们想给区间[3,5]的气球上色，所以我们执行了add(3,1)和add(6,-1)。
其实我们可以这样理解，如果更新区间[3,5]，那么我等于在3这个点+1,代表从3之后所有的点都增加了1。然后我们在6这个点-1表示从6之后所有的点都减少了1。所以达到了一个平衡的效果。最终实际+1的区间只是区间[3,5]内的数。
注明出处：http://blog.csdn.net/u013480600/article/details/21320487

关于树状数组：

树状数组一定是一个数据结构，他所能做的事情就是很快（以 logn 的时间）求得原数组 a [ ] 的某一区间 [ l , r ] 的所以值的“和”（这个“和”有引申含义）。所以做题的时候，一定要明确：这个 a [ ] 数 组我是拿它来做什么的；让 a [ ] 数组表示什么才能让这个求某区间 [ l , r ] 更有意义；如何设置 a [ ] 数组描述的事情才能让问题更加简化。这才是做一道题应该想的，而不是像办法用到树状数组，树状数组只是对于计算进行时间优化的一种方法，重点还是这个问题的计算方法或者处理办法。