树状数组

Circle

Description

You are given n points and two circles. The radius of the circle will be dynamical. Your task is to find how many points are under both circles at each time.

A point is under a circle iff the point is strictly inside the circle or on the border of the circle.

Input Description

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases.
For each case, the first line contains two integers n, m.(1 <= n, m <= 100000) Means the number of points and the number of queries.
Next n lines each contains two integer x, y(0 <= x, y <= 80000), describe a point.
Next line contains four integers x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 80000), describe the center of two circles.
Next m lines each line contains two integers R1, R2, describe the radius of two circles.(1 <= R1, R2 <= 100000)

Output Description

For each query, output the number of points under both circles.

Sample Input

Sample Output

0
3
0
4
碰见很多这样的题目了，哎，以为是几何题，题解出来了才发现是树状数组，多做做，多总结

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<string>
 6 #include<queue>
 7 #include<cmath>
 8 #include<vector>
 9 
10 using namespace std;
11 
12 #define mnx 104000
13 #define ll long long
14 #define inf 0x3f3f3f3f
15 #define lson l, m, rt << 1
16 #define rson m+1, r, rt << 1 | 1
17 
18 const int N = mnx;
19 struct point{
20     int x, y;
21     point( int x = 0, int y = 0 ) : x(x), y(y) {}
22     point operator - ( const point &b ) const {
23         return point( x - b.x, y - b.y );
24     }
25     int length(){
26         ll len = (ll)x * x + (ll)y * y;
27         ll pt = sqrt( len );
28         if( pt * pt < len ) pt++;
29         return (int)pt;
30     }
31     bool operator < ( const point & b ) const{
32         return x < b.x; 
33     }
34 }p[mnx], A, B;
35 struct rad{
36     int r1, r2, id;
37     bool operator < ( const rad & b ) const{
38         return r1 < b.r1;
39     }
40 }query[mnx];
41 int bit[mnx];
42 int sum( int x ){
43     int ret = 0;
44     while( x > 0 ){
45         ret += bit[x]; x -= x & -x;
46     }
47     return ret;
48 }
49 void add( int i, int x ){
50     while( i <= N ){
51         bit[i] += x;
52         i += i & -i;
53     }
54 }
55 int ans[mnx];
56 int main(){
57     int cas;
58     scanf( "%d", &cas );
59     while( cas-- ){
60         memset( bit, 0, sizeof(bit) );
61         int n, m;
62         scanf( "%d %d", &n, &m );
63         for( int i = 0; i < n; i++ ){
64             scanf( "%d %d", &p[i].x, &p[i].y );
65         }
66         scanf( "%d %d %d %d", &A.x, &A.y, &B.x, &B.y );
67         for( int i = 0; i < n; i++ ){
68             int dis1 = ( p[i] - A ).length();
69             int dis2 = ( p[i] - B ).length();
70             p[i] = point( dis1, dis2 );
71         }
72         sort( p, p + n );
73         for( int i = 0; i < m; i++ ){
74             scanf( "%d %d", &query[i].r1, &query[i].r2 );
75             query[i].id = i;
76         }
77         sort( query, query + m );
78         int j = 0;
79         for( int i = 0; i < m; i++ ){
80             while( j < n && p[j].x <= query[i].r1 ){
81                 add( p[j].y, 1 );
82                 j++;
83             }
84             ans[query[i].id] = sum( query[i].r2 );
85         }
86         for( int i = 0; i < m; i++ ){
87             printf( "%d
", ans[i] );
88         }
89     }
90     return 0;
91 }

View Code

http://acm.hdu.edu.cn/showproblem.php?pid=4417 hdu 4417 Super Mario

题意：给定一段区间每个点有个高度。在m次询问中每次给出左右端点和可以到达的高度，统计有多少个是小于到达高度

做法：离线排序+树状数组。。把输入的每个点的按高度排序，再把询问保存起来，按照高度排序，然后一边插入树状数组一边统计。。

其实还可以在线做，用主席树做

View Code