題目鏈接：點擊查看

題目大意：給出n個星星的坐標，規定每個星星的等級為在它左下方的星星的個數，輸出0~n-1每個等級共有多少個星星

題目分析：裸的線段樹，因為x坐標和y坐標都已經給排好序了，是按照y升序，當y相等時按照x升序排序，那么當輸入到任意一個星星的時候，我們看圖易知，之前錄入過的坐標中x小于等于當前坐標的都在當前坐標的左下角，所以我們可以按x坐標進行統計，有一個地方需要注意的就是，因為x坐標是從0開始的，所以我們要將所有的x坐標向右偏移一個單位來讓每個數都是正數，不然樹狀數組那里會出錯，還有一點就是，我們是按照坐標來建樹的，不是按照坐標數量，所以數組至少要開3e4+200，而不是1.5e4，不然會RE，直接分別上代碼吧：

線段樹：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=33000;int ans[N];struct Node {int l,r,sum; }tree[N<<2];void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].sum=0;if(l==r)return;int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void update(int k,int pos) {if(tree[k].l==tree[k].r){tree[k].sum++;return;}int mid=(tree[k].l+tree[k].r)>>1;if(mid>=pos)update(k<<1,pos);elseupdate(k<<1|1,pos);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l)return 0;if(tree[k].l>=l&&tree[k].r<=r)return tree[k].sum;return query(k<<1,l,r)+query(k<<1|1,l,r); }int main() { // freopen("input.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF){memset(ans,0,sizeof(ans));build(1,1,N);for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);x++;ans[query(1,1,x)]++;update(1,x);}for(int i=0;i<n;i++)printf("%d\n",ans[i]);}return 0; }

樹狀數組：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=33000;int n;int ans[N];int c[N];int lowbit(int x) {return x&-x; }void add(int pos) {while(pos<=N){c[pos]++;pos+=lowbit(pos);} }int query(int pos) {int ans=0;while(pos){ans+=c[pos];pos-=lowbit(pos);}return ans; }int main() { // freopen("input.txt","r",stdin);while(scanf("%d",&n)!=EOF){memset(ans,0,sizeof(ans));memset(c,0,sizeof(c));for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);x++;ans[query(x)]++;add(x);}for(int i=0;i<n;i++)printf("%d\n",ans[i]);}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2352 Stars(线段树/树状数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。