POJ2352——樹狀數組的應用

Stars

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 21050	Accepted: 9172

Description

Astronomers often examine starmaps where stars are represented by points on a plane and each star hasCartesian coordinates. Let the level of a star be an amount of the stars thatare not higher and not to the right of the given star. Astronomers want to knowthe distribution of the levels of the stars.

For example, look at the map shown on the figure above. Level of the starnumber 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4).And the levels of the stars numbered by 2 and 4 are 1. At this map there areonly one star of the level 0, two stars of the level 1, one star of the level2, and one star of the level 3.

You are to write a program that will count the amounts of the stars of eachlevel on a given map.

Input

The first line of the inputfile contains a number of stars N (1<=N<=15000). The following N linesdescribe coordinates of stars (two integers X and Y per line separated by aspace, 0<=X,Y<=32000). There can be only one star at one point of theplane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinatesare listed in ascending order of X coordinate.

Output

The output should contain Nlines, one number per line. The first line contains amount of stars of thelevel 0, the second does amount of stars of the level 1 and so on, the lastline contains amount of stars of the level N-1.

Sample Input

5

1 1

5 1

7 1

3 3

5 5

Sample Output

1

2

1

1

Hint

This problem has huge inputdata,use scanf() instead of cin to read data to avoid time limit exceed.

Source

Ural CollegiateProgramming Contest 1999

【題目大意】

在一個坐标系内，給若幹個點，每個點給定x、y坐标，定義點p的level為橫縱坐标均不超過點p的點的個數，輸出每個level包含的點的數量。

【我的算法】

不應用樹狀數組的時候，用兩個數組分别儲存輸入的橫坐标和縱坐标，然後用一個結構體的數組存儲輸入的結點。然後依次計算每一個結點的level值。

代碼如下：

#include <iostream>

using namespace std;

const int MAX= 32000;

int ArrayX[MAX]={0};

int ArrayY[MAX]={0};

struct Node

{

         int x;

         int y;

};

int Sum(int end, int* array)

{

         int sum = 0;

         while(end >= 0)

         {

                   sum+= array[end];

                   end--;

         }

         return sum;

}

int main()

{

         int N;

         cin>>N;

         int *count = new int[N-1];//結果計數

         struct Node *node = new struct Node[N];//存儲輸入的坐标點

         int x,y,i = 0, n = N;

         while (n-->0)

         {

                   cin>>x>>y;

                   node[i].x = x;

                   node[i++].y = y;

                   ArrayX[x]++;

                   ArrayY[y]++; 

         }

         for (int co= 0; co < N; co++)

         {

                   count[co] = 0;

         }

         for (int j = 0; j < N; j++)

         {

                   int  littleXNum,littleYNum, littleNum;

                   littleXNum= Sum(node[j].x-1, ArrayX);//計算比node結點橫坐标小的點的個數

                   littleYNum= Sum(node[j].y-1, ArrayY);//計算比node結點縱坐标小的點的個數

                   littleNum= littleXNum < littleYNum? littleXNum : littleYNum;//計算比node結點的橫坐标和縱坐标都小的點的個數

                   if(ArrayX[node[j].x] == 1&& ArrayY[node[j].y] == 1)//如果，此點的橫坐标和縱坐标上沒有其他點了則進行下一個結點的判斷

                   {

                            count[littleNum]++;

                            continue;

                   }

                   for(int k = 0; k < j; k++)//計算此點的橫坐标和縱坐标上其他符合條件的點

                   {

                            if (node[k].x == node[j].x && node[k].y <= node[j].y) //計算此點的縱坐标方向上其他符合條件的點

                                     littleNum++;

                            if (node[k].x <= node[j].x && node[k].y == node[j].y) //計算此點的橫坐标方向上其他符合條件的點

                                     littleNum++;

                   }

                   count[littleNum]++;

         }

         for (int c = 0; c < N; c++)

         {

                   cout<<count[c]<<endl;

         }

         system("pause");

         return0;

}

【錯誤原因分析】

原因：結果雖然正确，但是送出後TLE了。時間複雜度太高。沒有應用樹狀數組。

心得：好的資料結構來帶來高效的算法。

【正确算法】

       這道題目和計數有關，是典型的樹狀數組應用的題目。題目給的資料按照y排序，相同的y按照x排序，這就給解題帶來了很大的友善，我們可以按照坐标系中由下至上（y由小到大）、由左至右（x由小到大）的順序來處理資料，這樣我們隻利用x就可以進行計數了，因為當我們處理到任意點p的時候，所有的y小于p的點我們已經計數過了，隻需要統計所有x不超過p的點的數量就可以了。而這一步利用樹狀數組強大的計數功能實作。

        由于x的範圍是[0,32000]，可以申請一個長度為32001的計數數組sum，sum[i]表示x不大于i的點的數目，每次統計完i的數目後，要把sum[i]計數增加1。

代碼如下：

#include<iostream>

using namespace std;

#define N 32001

int sum[N+1];

//算這個^k有一個快捷的辦法，定義一個函數如下即可

//利用機器補碼的特點，這個函數可以改得更友善

int lowbit(int k)

{

         return k&(-k);

}

//如果要把a[i]增加v，可以通過調用如下函數實作

void add(int i,int v)

{

         while (i<=N)

         {

                   sum[i]+=v;

                   i+=lowbit(i);

         }

}

//如果要統計a[1]到a[i]之間的和，可以通過調用如下函數實作

int getSum(int i)

{

         int s=0;

         while (i>0)

         {

                   s+=sum[i];

                   i-=lowbit(i);

         }

         return s;

}

int main()

{

         int n,i,x,y;

         cin>>n; 

         int *result = new int[n];

         //初始化數組

         for(i=0;i<n;i++)

         {

                   result[i]=0;

         }

         for(i=1;i<=N;i++)

         {

                   sum[i]=0;

         }

         for(i=0;i<n;i++)

         {

                   cin>>x>>y;

                   result[getSum(x+1)]++;//統計

                   add((x+1),1); //更新sum[i]的值

         }

         for(i=0;i<n;i++)

         {

                   cout<<result[i]<<endl;

         }

         return1;

}