描述

数轴上有n个点，对于任一闭区间 [a, b]，试计算落在其内的点数。

输入

第一行包括两个整数：点的总数n，查询的次数m。

第二行包含n个数，为各个点的坐标。

以下m行，各包含两个整数：查询区间的左、右边界a和b。

输出

对每次查询，输出落在闭区间[a, b]内点的个数。

Example

Input

Output

限制

 ≤ n, m ≤ ×

对于次查询的区间[a, b]，都有a ≤ b

各点的坐标互异

各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数

时间： sec

内存： MB

 #include <cstdio>

 //#include <stdlib.h>

 //二分查找

 long binary_search(long* a, long len, long goal);

 void quicksort(long *a, long left, long right);

 //左边界T，右边界F

 long binary_search(long* a, long len, long goal, bool t)

 {

     long low = ;

     long high = len - ;

     long middle;

     while(low <= high)

     {

         middle = (low + high)/;

         if(goal == a[middle])

         {

             return (t ? middle: middle+);

         }

         else if(goal < a[middle])//在左半边

             high = middle - ;

         else//在右半边

             low = middle + ;

     }//low>high

     if(goal < a[middle])

         return middle;

     else//if (goal > a[middle])

         return middle + ;

 }

 void quicksort(long *a, long left,long right)

 {

     long i,j,t,temp;

     if(left>right)

        return; 

     temp=a[left]; //temp中存的就是基准数

     i=left;

     j=right;

     while(i<j)

     {

                    //顺序很重要，要先从右边开始找 小于基数的数

                    while(a[j]>=temp && i<j)

                             j--;

                    //再找左边的大于基数的数

                    while(a[i]<=temp && i<j)

                             i++;

                    //交换两个数在数组中的位置

                    if(i<j)

                    {

                             t=a[i];

                             a[i]=a[j];

                             a[j]=t;

                    }

     }

     //最终将基准数归位

     a[left]=a[i];

     a[i]=temp; 

     quicksort(a,left,i-);//继续处理左边的，这里是一个递归的过程

     quicksort(a,i+,right);//继续处理右边的 ，这里是一个递归的过程

 } 

 int main(void)

 {

     long num, cmd;

     long i,ret1,ret2;

     scanf("%ld %ld",&num,&cmd);

     //long *n = (long*)malloc(num*4);

     long *n = new long[num];

     for (i=;i<num;i++)

         scanf("%ld ",n+i);

     //long *src = (long*)malloc(cmd*4);

     //long *des = (long*)malloc(cmd*4);

     long *src = new long[cmd];

     long *des = new long[cmd];

     for (i=;i<cmd;i++)

         scanf("%ld %ld",src+i,des+i);

     quicksort(n, , num-);

 /*    for (i=0;i<num;i++)

         printf("%d ",n[i]);*/

     for (i=;i<cmd;i++)

     {

         ret1=binary_search(n,num,src[i],true);//find in n[], length num, goal src[i]

         ret2=binary_search(n,num,des[i],false);

         printf("%ld\n",ret2-ret1);

     }

     delete[] n;

     delete[] src;

     delete[] des;

     return ;

 }