题目:http://poj.org/problem?id=2352
大意:一些星星有自己的优先级,优先级是x坐标和y坐标小于等于该星星坐标的星星个数
思路:由于这个题的y值是从小到大排列,所以对x建立线段树,找小于等于该星星x坐标的星星个数即可
代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include <iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn=32010; const int man=15010; int res[man]; int tree[maxn*4]; int lz[maxn*4]; int num; int find(int l,int r,int w,int L,int R) { if(L<=l&&R>=r) { return tree[w]; } int m=(l+r)/2; int ans=0; if(L>m) ans+=find(m+1,r,w*2+1,L,R); else if(R<=m) { ans+=find(l,m,w*2,L,R); } else { ans+=find(l,m,w*2,L,m)+find(m+1,r,w*2+1,m+1,R); } return ans; } void update(int l,int r,int w,int x) { tree[w]++; if(x==l&&x==r) { return ; } int m=(l+r)/2; if(x<=m) update(l,m,w*2,x); else update(m+1,r,w*2+1,x); } int main() { int n; while(scanf("%d",&n)!=EOF) { int i; int x,y; memset(tree,0,sizeof(tree)); memset(lz,0,sizeof(lz)); memset(res,0,sizeof(res)); for(i=0;i<n;i++) { scanf("%d%d",&x,&y); x++; num=0; res[find(1,32005,1,1,x)]++; update(1,32005,1,x); } for(i=0;i<n;i++) { printf("%d ",res[i]); } } return 0; }