数星星

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>
 6 #include <cstdio>
 7 #include <queue>
 8 using namespace std ;
 9 
10 int n , q ;
11 struct id {
12     int x , y , sze ;
13 }; id star[100003] ;
14 int tot , c[1000007] , ans[100003] ;
15 bool out[100003] ;
16 
17 inline void Init (  ) {
18     freopen( "11349.in" , "r" , stdin ) ;
19     freopen( "11349.out" , "w", stdout ) ;
20 }
21 
22 
23 int cmp ( id a , id b ) {
24     return ( a.x < b.x||(a.x==b.x&&a.y<b.y) );
25 }
26 
27 
28 void input (  ) {
29     scanf( "%d" , &n ) ;
30     for ( int x = 1 ; x <= n ; x++ ) {
31         scanf( "%d%d" , &star[x].x , &star[x].y ) ;
32         star[x].y += 1 ;
33         star[x].sze = x ;
34     }
35 
36     sort( star + 1 , star + 1 + n , cmp ) ;
37     scanf( "%d" , &q ) ;
38 /*    for ( int x = 1 ; x <= q ; x++ ) {
39         int a ; scanf( "%d" , &a ) ;
40         out[a] = true ;
41     }*/
42 }
43 
44 
45 
46 int lowbit( int x ) {
47     return x &  (-x );
48 }
49 
50 int sum ( int x ) {
51     int tem = 0 ;
52     while( x > 0 ) {
53         tem += c[x] ;
54         x -= lowbit( x ) ;
55     }
56     return tem ;    
57 }
58 
59 
60 void update( int x , int add ) {
61     while( x <= 1000001 ) {
62         c[x] += add ;
63         x += lowbit( x ) ;
64     } 
65 }
66 
67 void sov(  ) {
68     memset( ans , -1 , sizeof( ans ) ) ;
69     for( int i = 1 ; i <= n ; ++i ) {
70         ans[ star[i].sze ] = sum ( star[i].y ) ;
71         update( star[i].y , 1 ) ;
72     }
73 }
74 
75 void output( ) {
76     for( int x = 1 ; x <= q ; x++  ) {
77         int a ; scanf( "%d" , &a ) ;
78         printf( "%d
" , ans[a] ) ;
79     }
80 }
81 
82 int main (  ) {
83 //    Init(  ) ;
84     input(  ) ;
85     sov(  ) ;
86     output(  ) ;
87 //    fclose(stdin);
88 //    fclose(stdout);
89     return 0 ;
90 }

天文学家们喜欢观察星星。它们把每颗星星看成一个点，并把每颗星星左下方（即横坐标和纵坐标都不比它大）的星星颗数作为它的等级值。现给出所有星星（星星个数为N）的坐标，计算并输出指定编号的星星的等级。注意：不存在相同坐标的星星

Input
第一行为N 后N行为编号为1到N的星星的坐标（坐标用整数）此后是M 后一行是M个星星的编号 N<=100000 M<=1000 坐标范围0<=x,y<=1000000
Output
要求依次输出这M个星星的等级，一行一个
Sample Input
5
0 0
2 0
3 0
1 1
2 2
2
4 5
Sample Output
1
3
50%的数据N<=1000;
100%人的数据N<=100000