题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1556

解题思路

方法一：差分与前缀和

差分与前缀和

这应该是入门学的吧。
为了回忆回忆加深一下印象，再稍微写一下。
区间[a,b]全部+1，就让存差值的数组c在a位置+1，b+1的位置-1。
c[i]=第i个数的值-第i-1个数的值。
输出i位置的值，求i位置的前缀和就行了。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int ball[N];
int n;
int main(){
    while(cin>>n&&n){
        memset(ball,0,sizeof ball);
        for(int i=1;i<=n;i++){
            int a,b;
            cin>>a>>b;
            ball[a]++;
            ball[b+1]--;
        }
        for(int i=1;i<=n;i++)
            ball[i]+=ball[i-1];

        for(int i=1;i<n;i++)
            cout<<ball[i]<<' ';
        cout<<ball[n]<<endl;//题目没说，但是好像要求输出结尾不能有空格，有空格没法AC        
    }
}

方法二：树状数组

区间修改，单点查询：

getsum用于求前缀和；update用于更改端点的值；
本质上，与差分前缀和是一样的。
差分思想，通过树状数组体现！

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int c[N],n;
int lowbit(int x){
    return x&(-x);
}
void update(int x,int add){
    while(x<=n){
        c[x]+=add;
        x+=lowbit(x);
    }
}
int getsum(int x){
    int ans=0;
    while(x>0){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    int a,b;
    while(cin>>n&&n){
        memset(c,0,sizeof c);
        for(int i=1;i<=n;i++){
            cin>>a>>b;
            update(a,1);
            update(b+1,-1);
        }        
        for(int i=1;i<n;i++)
            cout<<getsum(i)<<' ';
        cout<<getsum(n)<<endl;
    }
}