LOJ 1088 Points in Segments

題目大意：

        給定n個點（1 ≤ n ≤ 10^5），每個點都有一個整數值，範圍是[0, 10^8]，并且已經升序排列好了（每個點的值互不相同），現在給定q個段[a, b]，其中a、b∈[0, 10^8]，計算序列中每個給定段中點的個數，即p∈序列，且a ≤ p ≤ b的p的個數。

       現有多個測例（測例數會給出），每個測例中都給出n和q，以及n個元素的大小（升序排列輸入的）以及q個段的左端值和右端值a和b，對于每個測例的每個段都給出位于段中的元素的個數。

題目連結

C語言實作lower_bound和upper_bound：

注釋代碼：

/*                                      
 * Problem ID : LOJ 1088 Points in Segments  
 * Author     : Lirx.t.Una                                      
 * Language   : C++                     
 * CPU		  : 0.340                                      
 * Memory	  : 1476                                      
*/ 

#include <stdio.h>

//點集的最大長度
#define MAXN        100000
 
int     a[MAXN];
 
int
xbsrch( int lft, int rht, int x ) {//binary search in x
	//搜出大于等于x的第一個元素,即lower_bound
 
    int     mid;
 
    while ( lft < rht ) {
   
        mid = ( lft + rht ) >> 1;
 
        if ( a[mid] >= x )//一旦大于等于x就将區間置為左部
            rht = mid;//此步保證結果位置一定最左
        else//小于就mid左移
			//此步保證了結果位置的元素一定大于等于x			
            lft = mid + 1;
    }
 
    return lft;
}
 
int
ybsrch( int lft, int rht, int y ) {//binary search in y
	//搜出大于y的第一個元素,即upper_bound
 
    int     mid;
 
    while ( lft < rht ) {
   
        mid = ( lft + rht ) >> 1;
 
        if ( a[mid] > y )//一旦大于y就将區間置為右部
            rht = mid;//此步保證結果位置一定最右
        else//小于等于就mid右移
			//此步保證了結果一定大于y
            lft = mid + 1;
    }
 
    return lft;
}
 
int
main() {
 
    int     nscn, iscn;
    int     n, k;//n個點k個段
    int     x, y;//搜查的左右端點
 
    int     p1, p2;//搜查結果的左右端點的數組下标
 
    int     i;
 
    scanf("%d", &nscn);
    iscn = 0;
 
    while ( nscn-- ) {
   
        scanf("%d%d", &n, &k);
        for ( i = 0; i < n; i++ )
            scanf("%d", a + i);
 
        printf("Case %d:\n", ++iscn);
        while ( k-- ) {
       
            scanf("%d%d", &x, &y);
			
            if ( a[n - 1] < x || a[0] > y ) {
				//如果搜查區間和點序列不重合
				//則無任何元素
				
                puts("0");
                continue;
            }
			
			//特殊情況（y的srch不能正确處理這種特殊情況）
            if ( x <= a[0] )//當左搜查元素小于等于序列最左端值
                p1 = 0;//則左坐标就直接等于0（0号元素就是大于等于x的第一個元素了）
            else
                p1 = xbsrch( 0, n - 1, x );
			
            if ( y >= a[n - 1] )//對于這種情況若使用ysrch，則其傳回的就是
				//序列的最後一個元素，而不是最後一個元素的後一個位置
                p2 = n;
            else
                p2 = ybsrch( p1, n - 1, y );//利用p1作為左端點，可以剪短搜尋範圍以節省時間
			
            printf("%d\n", p2 - p1);
        }
    }
	
    return 0;
}
           

無注釋代碼：

#include <stdio.h>
 
#define MAXN        100000
 
int     a[MAXN];
 
int
xbsrch( int lft, int rht, int x ) {
 
    int     mid;
 
    while ( lft < rht ) {
   
        mid = ( lft + rht ) >> 1;
 
        if ( a[mid] >= x )
            rht = mid;
        else
            lft = mid + 1;
    }
 
    return lft;
}
 
int
ybsrch( int lft, int rht, int y ) {
 
    int     mid;
 
    while ( lft < rht ) {
   
        mid = ( lft + rht ) >> 1;
 
        if ( a[mid] > y )
            rht = mid;
        else
            lft = mid + 1;
    }
 
    return lft;
}

int
main() {
	
    int     nscn, iscn;
    int     n, k;
    int     x, y;
	
    int     p1, p2;
	
    int     i;
	
    scanf("%d", &nscn);
    iscn = 0;
	
    while ( nscn-- ) {
		
        scanf("%d%d", &n, &k);
        for ( i = 0; i < n; i++ )
            scanf("%d", a + i);
		
        printf("Case %d:\n", ++iscn);
        while ( k-- ) {
			
            scanf("%d%d", &x, &y);
			
            if ( a[n - 1] < x || a[0] > y ) {
				
                puts("0");
                continue;
            }
			
            if ( x <= a[0] )
                p1 = 0;
            else
                p1 = xbsrch( 0, n - 1, x );
			
            if ( y >= a[n - 1] )
                p2 = n;
            else
                p2 = ybsrch( p1, n - 1, y );
			
            printf("%d\n", p2 - p1);
        }
    }
	
    return 0;
}
           

使用lower_bound和upper_bound二分搜尋模闆函數：

/*                                      
 * Problem ID : LOJ 1088 Points in Segments  
 * Author     : Lirx.t.Una                                      
 * Language   : C++                     
 * CPU	      : 0.364                                      
 * Memory     : 2076                                      
*/ 

#include <algorithm>
#include <iostream>
#include <cstdio>

#define MAXN        100001

using namespace std;

int     a[MAXN];

int
main() {
	
    int     nscn, iscn;
    int     n, k;
    int     x, y;
	
    int     p1, p2;
	
    int     i;
	
    scanf("%d", &nscn);
    iscn = 0;
	
    while ( nscn-- ) {
		
        scanf("%d%d", &n, &k);
		
        for ( i = 0; i < n; i++ )
            scanf("%d", a + i);
		
        printf("Case %d:\n", ++iscn);
        while ( k-- ) {
			
            scanf("%d%d", &x, &y);
			
            p1 = lower_bound(a, a + n, x) - a;
            p2 = upper_bound(a + p1, a + n, y) - a;
			
            printf("%d\n", p2 - p1);
        }
    }
	
    return 0;
}
           

單詞解釋：

dimensional：adj, 次元的，空間上的

n dimensional：adj, n維的