共计 2906 个字符，预计需要花费 8 分钟才能阅读完成。
二分法咱们都晓得，二分的根本过程如下（_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;
//}