POJ 1541 Stars（樹狀數組）

題目傳送門

• 才入門樹狀數組，沒有搞懂這個題和樹狀數組有什麼聯系，其實這個題雖然給的是一個二維的圖，但是可以把它放到一維來看，首先他給出的x，y是有順序的，y一定的時候，後面給出的一定比前面的level高，而這裡的y一定的情況下按照x的順序排列，是以就可以把他當成一個x軸

  下面用題目的樣例來解釋

5
1 1
5 1
7 1
3 3
5 5
           

首先y等于1的時候，輸入x

這個時候查找x前面所有的和就是它的level

此時level0=1，level1=1，level2=1；

1	5	7//對應的x
1	1	1//對應的樹狀數組
           

然後輸入y等于3的時候，就插進去一個x=3

level2+1=2

1	3	5	7
1	1	1	1
           

y=5的時候，插進去x=5，已經存在了，這個時候把5這裡的樹狀數組的值更新為加1

level3=1

1	3	5	7
1	1	2	1
           

完整代碼

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<vector>
#include<queue>
#include<string>
#include <cmath>
#include<set>
#define mod 999997
#define lson l, mid, root << 1
#define rson mid + 1, r, root << 1 | 1
#define father  l , r , root
#define lowbit(x) ( x & ( - x ) )
using namespace std;
typedef long long ll;
const int maxn = 32010;
const int inf = 0x3f3f3f3f;

int cnt[maxn];
int a[maxn];

int sum(int x){
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i)){
        ans+=a[i];
    }
    return ans;
}

void update(int x){

    for(int i=x;i<=maxn;i+=lowbit(i)){
        a[i]++;
    }

}

int main( ){
   int n;
   while(~scanf("%d",&n)){
        //scanf("%d",&n);
        memset(cnt,0,sizeof(cnt));
        memset(a,0,sizeof(a));
        for(int i=0;i<n;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            cnt[sum(x+1)]++;
            update(x+1);//更新該位置的值+1
        }
        for(int i=0;i<n;i++){
            printf("%d\n",cnt[i]);
        }
   }
   return 0;
}