二分法咱们都晓得，二分的根本过程如下（_merge（）见下）：

//void erfen(int l,int r){//二分递归之后归并 //    int mid;//    mid = (l + r) / 2;//    if(l < r){//        erfen(l,mid);//        erfen(mid + 1,r);//    }//    _merge(l,mid,r);//}

Points in Segments（二分分治）

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 pi will lie in a segment A B if A ≤ pi ≤ B.

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.

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 ≤ 105) 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, 108].

Each of the next q lines contains two integers Ak Bk (0 ≤ Ak ≤ Bk ≤ 108) 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
1
5 3
1 4 6 8 10
0 5
6 10
7 100000

Case 1:
2
3
2

#include<iostream>#include<algorithm>#include<string>#include<string.h>#include<cstdio>#include<queue>#include<stack> #include<set> #include<vector> using namespace std;/*lower_bound( begin,end,num)：从数组的begin地位到end-1地位二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,失去找到数字在数组中的下标。upper_bound( begin,end,num)：从数组的begin地位到end-1地位二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,失去找到数字在数组中的下标。*/int a[100010];int main(){    int t = 0;    scanf("%d",&t);    for(int i = 1; i <= t; i++){        int n1,n2;        scanf("%d %d",&n1,&n2);//        int a[100010];        for(int j = 0; j < n1; j++){            scanf("%d",&a[j]);        }        printf("Case %d:\n",i);        while(n2--){            int q1,q2,ans1,ans2;            scanf("%d %d",&q1,&q2);            ans1 = (int)(upper_bound(a,a + n1,q2) - a);//最大值处用upper_bound必须找到比他大的那个地位 //            ans1 = (int)(lower_bound(a,a + n1,q2) - a);            ans2 = (int)(lower_bound(a,a + n1,q1) - a);//最小值处用lower_bound就能够，找到等于他的的那个地位就能够             printf("%d\n",ans1 - ans2);        }    }    return 0;}

逆序对个数（归并排序）

给出一个数组a，问这个数组中有多少个逆序对。
逆序对定义：若i<j且a[i]>a[j],则(a[i],a[j])是一个逆序对。
如数组3 4 1 2中的逆序对有(3,1),(3,2),(4,1),(4,2)，共4个逆序对。
Input
第一行一个整数n，示意元素个数。
第二行n个空格分隔的整数a[i]。
Output
一个数，示意逆序对个数。
Sample Input 1
5
3 3 4 1 2
Sample Output 1
6
Hint
50%的数据 n ≤ 6000.
————————————————
参考自https://blog.csdn.net/qq_4464...

//#include<iostream>//#include<algorithm>//#include<string>//#include<string.h>//#include<cstdio>//#include<queue>//#include<stack> //#include<set> //#include<vector> //using namespace std;//int a[100010],b[100010];//long long n,ans;//void _merge(int l,int mid,int r){//归并排序代码 //    int p1,p2;//    p1 = l;//    p2 = mid + 1;//    for(int i = l; i <= r; i++){//        b[i] = a[i];//    }//    int x;//    for( x = p1; p1 <= mid && p2 <= r; x++){//        if(b[p1] > b[p2]){//            ans += mid - p1 + 1;//计算逆序数对数 //            //参考https://blog.csdn.net/qq_44643644/article/details/105880856//            a[x] = b[p2++];////            cout << ans << x << endl;//        }else{//            a[x] = b[p1++];//        }//    }//    while(p1 <= mid){//前半表未取完，持续 //        a[x++] = b[p1++];//    }//    while(p2 <= mid){//后半表未取完，持续//        a[x++] = b[p2++];//    }    //} //void erfen(int l,int r){//二分递归之后归并 //    int mid;//    mid = (l + r) / 2;//    if(l < r){//        erfen(l,mid);//        erfen(mid + 1,r);//    }//    _merge(l,mid,r);//}//int main(){//    scanf("%lld",&n);//    for(int i = 1; i <= n; i++){//        scanf("%d",&a[i]);//    }//    erfen(1,n);//    printf("%lld\n",ans);//    return 0;//}