从 8 月初就看到了这题, 今天猛然想起来, 然后把补上了
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<queue>
- #include<map>
- #include<iomanip>
- #include<algorithm>
- #include<vector>
- #define INF 2e9
- #define maxnode 100000
- #define ll long long
- #define lowbit(x) (x&(-x))
- int dx[4]={0,0,1,-1};
- int dy[4]={1,-1,0,0};
- using namespace std;
- int c[100010];
- void update(int index,int dx){
- for(;index<=100005;index+=lowbit(index)){
- c[index]+=dx;
- }
- }
- int getSum(int n){
- int ans=0;
- for(;n>0;n-=lowbit(n)) ans+=c[n];
- return ans;
- }
- struct node{
- int x,y,id;
- node(int x1=0,int y1=0,int i1=0): x(x1),y(y1),id(i1) {}
- bool operator <(const node &n1)const{
- if( x==n1.x ) return y>n1.y;
- return x<n1.x;
- }
- }cow[100005];
- int ans[100005];
- int main(){
- iOS::sync_with_stdio(false);
- while(1){
- int n; cin>>n;
- if(n==0) break;
- for(int i=1;i<=n;i++){
- int s,e; cin>>s>>e;
- cow[i]=node(s,e,i);
- }
- sort(cow+1,cow+1+n);
- memset(c,0,sizeof(c));
- for(int i=1;i<=n;i++){
- if( (cow[i].x==cow[i-1].x) && (cow[i].y==cow[i-1].y) ) {
- ans[ cow[i].id ] = ans[ cow[i-1].id ];
- update(cow[i].y,1);
- }
- else{
- ans[ cow[i].id ] = getSum(100005)-getSum( cow[i].y-1 );
- update(cow[i].y,1);
- }
- }
- for(int i=1;i<=n;i++) cout<<ans[i]<<" "; cout<<endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2799895.html