这个题目本质上要解决一个问题，给出一些区间[ai, bi)和一个数组，求数组中每个元素被区间覆盖的次数。
一开始想了个做法是线段树，后来想了个O(n)的做法。具体过程如下：
1。去掉重复区间
2。f数组置0
3。对每个区间[ai, bi)，令f[ai]++，f[bi]--
4。设答案数组为c，则c[i] = sum(f[j]), 1 <= j <= i
关键是理解f数组的意义：f[i]表示第i个点对后续点的影响，而f[ai]++，f[bi]--保证了区间外的点不受影响，区间内的点都受+1的影响
以下是我的代码：
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2008-1-12 21:14:15
File Name: pku3263.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxr = 10010;
const int maxn = 10010;
struct node_t
{
int l, r;
};
bool operator ==(const node_t &a, const node_t &b)
{
return a.l == b.l && a.r == b.r;
}
bool operator <(const node_t &a, const node_t &b)
{
return a.l < b.l || a.l == b.l && a.r < b.r;
}
node_t p[maxr];
int f[maxn];
int a[maxn];
int n, I, H, r;
int main()
{
scanf("%d%d%d%d", &n, &I, &H, &r);
for (int i = 0; i < r; i++)
{
scanf("%d%d", &p[i].l, &p[i].r);
if (p[i].l > p[i].r)
swap(p[i].l, p[i].r);
}
sort(p, p + r);
r = unique(p, p + r) - p;
memset(f, 0, sizeof(f));
for (int i = 0; i < r; i++)
{
f[p[i].l + 1]--;
f[p[i].r]++;
}
a[0] = 0;
for (int i = 1; i <= n; i++)
a[i] = a[i - 1] + f[i];
for (int i = 1; i <= n; i++)
printf("%d\n", a[i] + H);
return 0;
}