程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1556 Color the ball 樹狀數組

hdu 1556 Color the ball 樹狀數組

編輯:C++入門知識

這個題的意思是給定一個長為N的區間。不斷的給某個子區間[A,B]中的每個點塗一次色。最後問每個點的塗色次數。
   這個題貌似可以擴展到多維的情況,但是多維的情況下必須用樹狀數組求和以加快速度,一維的情況直接求和即可。
   假如,第一次塗色是對區間[A,B]塗色一次,可以讓nNum[nA]++,nNum[nB+1]--即可。因為這樣對於區間[0,nA-1]的任意值i有
都要nNum[1]+nNum[2]+...+nNum[i] = 0。而對於區間[nA,nB]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。
對於區間[nB+1, nN]的任意值i有nNum[1]+nNum[2]+...+nNum[i] = 0。
   那麼重復多次了。如果上述求和nNum[1]+nNum[2]+...+nNum[i] 剛好代表每個結點i的塗色次數,那麼這個題就可解了。
   用例子驗證一下,發現肯定是這樣的。證明略了。
   至於樹狀數組網上一大堆資料。樹狀數組模板單一,敲代碼太方便了。

   代碼如下:
#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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved