HDOJ 1556( 絕對原創且通俗的講解 )

題目很簡單，普通的思路也很簡單，不過這種思路一定是超時的！這道題，卡了一個多月，嘗試在網上找一些題解，但是代碼老長了，說是用到了線段樹之類的高級的東西，確實還不懂。最後發現了一種很簡單的代碼，一開始真心看不懂，鑽研許久，終於看懂了，我的這一篇博文應該是第一篇比較詳細地解釋這個問題的，下面是我的思考！

在這種高效的實現中，用到了累加的思想！他的做法就是在所給的閉區間的起點，用一個數組表示再以該起點以及之後的值都要自增一次。舉個例子，給一個區間[ a, b ]，則使用一個數組sum[a]++;( 起始值都為零 )，說明a以及之後的總值都要加一，但是b之後的值不用加一，所以sum[b+1]--表示b以後的值自減( 因為前面的sum[a]++ 已經使b後面的值自增了，所以在這裡要減掉 )。如果你到這裡還不懂的話，請注意我前面提到的一個詞——“累加”。我們所要的sum[]數組，就是記錄當前點以及後面的點被加了多少次( 右端點多加的也是通過sum[]數組來減去多加的！ )。通過這種做法，我們可以很簡單高效的解決這一道問題而不用用到線段樹這種高級的數據結構！不得不感歎一句人類真是偉大！

說了這麼多，不知你懂了沒？下面是代碼：

#include 
#include 
#define N 100001

using namespace std;

int main()
{
    int n;
    while( scanf( "%d", &n ) && n != 0 )
    {
        int sum[N] = {0};
        int l, r;
        int ans = 0;

        for( int i = 0; i < n; i++ )
        {
            scanf( "%d%d", &l, &r );
            sum[l]++;
            sum[r+1]--;
        }
        for( int i = 1; i <= n; i++ )
        {
            ans += sum[i];
            printf( "%d", ans );
            if( i != n )
            {
                putchar( ' ' );
            }
        }
        putchar( '\n' );
    }
    return 0;
}