lightoj1088

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

27 8月 2015

1088 - Points in Segments

For example if the points are 1, 4, 6, 8, 10. And the segment is 0 to 5. Then there are 2 points that lie in the segment.Given n points (1 dimensional) and q segments, you have to find the number of points that lie in each of the segments. A point p_i will lie in a segment A B if A ≤ p_i ≤ B.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 10⁵) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers denoting the points in ascending order. All the integers are distinct and each of them range in [0, 10⁸].

Each of the next q lines contains two integers A_k B_k (0 ≤ A_k ≤ B_k ≤ 10⁸) denoting a segment.

Output

For each case, print the case number in a single line. Then for each segment, print the number of points that lie in that segment.

Sample Input

Output for Sample Input

15 31 4 6 8 100 5

6 10

7 100000

Case 1:232

Note

Dataset is huge, use faster I/O methods.

题目类型：二分法

算法分析：读入数据，然后二分求得所求区间的上下界在输入序列中的下标pos_low和pos_high，最后直接pos_high – pos_low即可

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

const int maxn = 100000 + 66;

int ans[maxn];

int n, q;

int Calc_low (int val)
{
    int low = 0, high = n - 1, mid;

    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (val <= ans[mid])
            high = mid - 1;

        else
            low = mid + 1;
    }

return low;
}

int Calc_high (int val)
{
    int low = 0, high = n - 1, mid;

    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (val >= ans[mid])
            low = mid + 1;

        else
            high = mid - 1;
    }

return low;
}

int main()
{
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;

    scanf ("%d", &t);

    while (t--)
    {


        scanf ("%d%d", &n, &q);

        int i;
        for (i = 0; i < n; i++)
            scanf ("%d", &ans[i]);

        printf ("Case %d:\n", flag++);

        int val_low, val_high;
        for (i = 0; i < q; i++)
        {
            scanf ("%d%d", &val_low, &val_high);

            int pos_low = Calc_low (val_low);
            int pos_high = Calc_high (val_high);

            printf ("%d\n", pos_high - pos_low);
        }
    }

return 0;
}

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

const int maxn = 100000 + 66;

int ans[maxn];

int n, q;

int Calc_low (int val)

{

int low = 0, high = n - 1, mid;

while (low <= high)

{

mid = low + (high - low) / 2;

if (val <= ans[mid])

high = mid - 1;

else

low = mid + 1;

}

return low;

}

int Calc_high (int val)

{

int low = 0, high = n - 1, mid;

while (low <= high)

{

mid = low + (high - low) / 2;

if (val >= ans[mid])

low = mid + 1;

else

high = mid - 1;

}

return low;

}

int main()

{

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

scanf ("%d%d", &n, &q);

int i;

for (i = 0; i < n; i++)

scanf ("%d", &ans[i]);

printf ("Case %d:\n", flag++);

int val_low, val_high;

for (i = 0; i < q; i++)

{

scanf ("%d%d", &val_low, &val_high);

int pos_low = Calc_low (val_low);

int pos_high = Calc_high (val_high);

printf ("%d\n", pos_high - pos_low);

}

return 0;

}

lightoj1083

lightoj1112

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨