這個題的意思是給定一個長為N的區(qū)間。不斷的給某個子區(qū)間[A,B]中的每個點涂一次色。最后問每個點的涂色次數(shù)。
這個題貌似可以擴展到多維的情況，但是多維的情況下必須用樹狀數(shù)組求和以加快速度，一維的情況直接求和即可。
假如，第一次涂色是對區(qū)間[A,B]涂色一次，可以讓nNum[nA]++,nNum[nB+1]--即可。因為這樣對于區(qū)間[0,nA-1]的任意值i有
都要nNum[1]+nNum[2]+...+nNum[i] = 0。而對于區(qū)間[nA,nB]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。
對于區(qū)間[nB+1, nN]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。
那么重復(fù)多次了。如果上述求和nNum[1]+nNum[2]+...+nNum[i] 剛好代表每個結(jié)點i的涂色次數(shù)，那么這個題就可解了。
用例子驗證一下，發(fā)現(xiàn)肯定是這樣的。證明略了。
至于樹狀數(shù)組網(wǎng)上一大堆資料。樹狀數(shù)組模板單一，敲代碼太方便了。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <algorithm>
using namespace std;
int nNum[100000 + 10];
int nN;
int LowBit(
int nI)
{
return nI & (-nI);
}
void Add(
int nI,
int nAdd)
{
while (nI <= nN)
{
nNum[nI] += nAdd;
nI += LowBit(nI);
}
}
int GetSum(
int nI)
{
int nAns = 0;
while (nI > 0)
{
nAns += nNum[nI];
nI -= LowBit(nI);
}
return nAns;
}
int main()
{
int nA, nB;
while (scanf("%d", &nN), nN)
{
memset(nNum, 0,
sizeof(nNum));
for (
int i = 1; i <= nN; ++i)
{
scanf("%d%d", &nA, &nB);
Add(nA, 1);
Add(nB + 1, -1);
}
for (
int i = 1; i <= nN; ++i)
{
printf("%d%s", GetSum(i), i == nN ? "\n" : " ");
}
}
return 0;
}