題意：

m個星星，一個星星的等級取決于有多少其他星星的橫縱坐標不大于它，如果有x個，該星星等級為x
問各個等級的星星有多少個？
（題目會按照y的升序給出星星坐標）

題解：

樹狀數(shù)組入門題（不要問我為什么又開始做入門題。。。好久沒做樹狀數(shù)組都忘干凈了）
因為題目會按照y的升序給出星星坐標，所以星星A后面輸入的x，y不可能都小于星星A，我們只需要在樹狀數(shù)組中找小于等于3的值即可，A[i]表示x坐標為i的個數(shù)，C[]為A[]的樹狀數(shù)組，那么GetSum(i)就是 序列中前i個元素的和，即x小于等于i的星星數(shù)。
記得將x坐標統(tǒng)一加一，因為有可能x坐標為0。。

代碼：

#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int maxn = 32005; int a[maxn], level[maxn], C[maxn]; int lowbit(int x) {return x&(-x); } void Update(int i, int value) {while(i <= maxn){C[i] += value;i += lowbit(i);} } int getsum(int i) {int s = 0;while(i > 0){s += C[i];i -= lowbit(i);}return s; } int main() {int n;while(cin >> n){int x, y;memset(a, 0, sizeof(a));memset(level, 0, sizeof(level));memset(C, 0, sizeof(C));for(int i = 1; i <= n; i++){scanf("%d%d", &x,&y);int le = getsum(x+1);a[x+1]++;Update(x+1, 1);//更新 printf("le=%d\n",le);level[le]++;}for(int i = 0; i < n; i++)cout << level[i] << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Stars（树状数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。