這個題目本質上要解決一個問題，給出一些區間[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;
}