前面用樹狀數(shù)組寫了下，這次又線段樹寫。
發(fā)現(xiàn)線段樹如果學(xué)的好的話，那么這題應(yīng)該代碼量不大，不然代碼量比較大，至少比樹狀數(shù)組大。
這題要說的就是線段樹里存的信息了，我存的是[left,right]里面所含的星星數(shù)
CODE
1/**//*
2
ID:Klion
3 PRO:POJ_2352
4 LANG:C++
5
*/
6
#include <iostream>
7using namespace std;
8int level[15002];
9int tree[32000*4];//線段樹內(nèi)存要求基本是n*4
10int find(int i,int x,int left = 0,int right = 32000)
11
{
12 tree[i]++;
13 if(x == right)
14 return tree[i]-1;//減去自己
15 int mid = (left + right) >> 1;
16 if(x <= mid)
17 return find(i<<1,x,left,mid);
18 else
19 return tree[i<<1]+find((i<<1) + 1,x,mid+1,right);
20}
21int main(void)
22{
23 int n;
24 int x,y;
25 scanf("%d",&n);
26 for(int i = 0;i < n;i++)
27
{
28 scanf("%d%d",&x,&y);
29 level[find(1,x)]++;//查詢，插入一并操作
30
}
31 for(int i = 0;i < n;i++)
32 printf("%d\n",level[i]);
33 return 0;
34}
35