這個(gè)題目本質(zhì)上要解決一個(gè)問題，給出一些區(qū)間[ai, bi)和一個(gè)數(shù)組，求數(shù)組中每個(gè)元素被區(qū)間覆蓋的次數(shù)。
一開始想了個(gè)做法是線段樹，后來想了個(gè)O(n)的做法。具體過程如下：
1。去掉重復(fù)區(qū)間
2。f數(shù)組置0
3。對(duì)每個(gè)區(qū)間[ai, bi)，令f[ai]++，f[bi]--
4。設(shè)答案數(shù)組為c，則c[i] = sum(f[j]), 1 <= j <= i
關(guān)鍵是理解f數(shù)組的意義：f[i]表示第i個(gè)點(diǎn)對(duì)后續(xù)點(diǎn)的影響，而f[ai]++，f[bi]--保證了區(qū)間外的點(diǎn)不受影響，區(qū)間內(nèi)的點(diǎn)都受+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;
}