POJ 2352 Stars (線段樹(shù))

手動(dòng)博客搬家：本文發(fā)表于20170819 22:11:49, 原地址https://blog.csdn.net/suncongbo/article/details/77417650

URL: http://poj.org/problem?id=2352

題目大意:給定n個(gè)點(diǎn)(n<=15000), 每個(gè)點(diǎn)有坐標(biāo)(x, y) (0<=x, y<=32000), 規(guī)定每個(gè)點(diǎn)i的level等于滿(mǎn)足x[j]<=x[i] && y[j]<=y[i]的點(diǎn)j的個(gè)數(shù)，求出level值為0, 1, 2, ..., n-1的點(diǎn)分別有幾個(gè). y以升序給出, y值相等的以x升序給出。

思路分析:既然y值以升序給出，那問(wèn)題就簡(jiǎn)化成了: 給定一個(gè)數(shù)列a, 求a[1]至a[i-1]共有多少個(gè)數(shù)在[0, i]之間。
(然后統(tǒng)計(jì)一下即可)不難觀察到，線段樹(shù)很適合處理此類(lèi)問(wèn)題。
把坐標(biāo)看成區(qū)間，對(duì)[0,32000]的區(qū)間建線段樹(shù)，樹(shù)中的num記錄[l, r]區(qū)間內(nèi)的x的個(gè)數(shù)。
(也可對(duì)[0,maxx]區(qū)間建樹(shù)，但是要先求出maxx)每次添加新的節(jié)點(diǎn)，找到x應(yīng)該所在的那個(gè)節(jié)點(diǎn)，然后沿著遞歸之路每到一個(gè)節(jié)點(diǎn)就num++, 直到找到為止。
每次添加之前先詢(xún)問(wèn)，詢(xún)問(wèn)時(shí)求出區(qū)間[0,x]所跨子區(qū)間的num值之和。
由此算出level, 然后統(tǒng)計(jì)即可。
時(shí)間復(fù)雜度O(n log n).

部分易錯(cuò)點(diǎn)：

線段樹(shù)區(qū)間從0開(kāi)始，而不是1.

線段樹(shù)的數(shù)組要開(kāi)MAXN的4倍，MAXN = 32000 but not 15000

代碼呈現(xiàn)：(Time: 188 MS; Memory: 2248 K; Code: 1452 B)

#include<cstdio> #include<algorithm> using namespace std;const int MAXN = 32000; struct Node {int left,right,num,tag; }; int lvl[MAXN+2]; struct SegmentTree {Node nd[MAXN*4+2];void init(){for(int i=1; i<=MAXN*4; i++){nd[i].left = nd[i].right = nd[i].num = 0;}}void build(int lbound,int rbound,int pos){nd[pos].left = lbound;nd[pos].right = rbound;if(lbound==rbound) return;int mid = (lbound+rbound)/2;build(lbound,mid,2*pos);build(mid+1,rbound,2*pos+1);}void addval(int lbound,int rbound,int val,int pos){nd[pos].num++;if(lbound==rbound) return;int mid = (nd[pos].left+nd[pos].right)/2;if(val<=mid) addval(lbound,mid,val,2*pos);else addval(mid+1,rbound,val,2*pos+1);}int query(int lbound,int rbound,int pos){int mid = (nd[pos].left+nd[pos].right)/2;if(lbound==nd[pos].left && rbound==nd[pos].right) return nd[pos].num; long long ans;if(rbound<=mid) ans = query(lbound,rbound,2*pos);else if(lbound>mid) ans = query(lbound,rbound,2*pos+1);else ans = query(lbound,mid,2*pos)+query(mid+1,rbound,2*pos+1);return ans;} }; SegmentTree st; int a[MAXN+2]; int n;int main() {int q,lbound,rbound,val;char flag[5];scanf("%d",&n);st.init();st.build(0,MAXN,1); //can be both [0,MAXN] or [0,MAXX]; MAXX is the maximum value of all xfor(int i=1; i<=n; i++){int x,y;scanf("%d%d",&x,&y);lvl[st.query(0,x,1)]++; //must be [0,x]st.addval(0,MAXN,x,1);}for(int i=0; i<n; i++){printf("%d\n",lvl[i]);} return 0; } 發(fā)表于 2018-12-26 22:34 suncongbo 閱讀(...) 評(píng)論(...) 編輯 收藏 刷新評(píng)論刷新頁(yè)面返回頂部

總結(jié)

以上是生活随笔為你收集整理的POJ 2352 Stars (线段树)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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