具体说下二分 二分是在一个有单调性的序列上进行查询的算法 一般有两类查询要求 一类是给一个定值x，找到序列中的第一个数k，使得k >= x，即x后面紧挨的一个数（后继） 第二类是找到一个k，使得k最大且 k <= x 二分最难的地方在于边界判断 对于第一类： 设变量L, R 表示当前序列左端和右端，初值为1和n，设 mid = (L + R) / 2（C++自带向下取整）
以mid为分界线将序列分为两半（一般都认为mid属于左半边），若a[mid] >= x，即mid位置的元素符合要求 那么答案所在的区间一定属于[L, mid] ，于是我们使 R = mid 若a[mid] < x，mid位置元素不符合要求， 则答案所属区间一定在[mid+1, R]里面，使L = mid + 1
但是为什么要一定要写判断a[mid] >= x，然后改变R呢？为什么不是写 a[mid] <= x，然后改变L？ 因为现在我们有一种办法能不断缩小答案所在的区间，并且那么这个区间在缩小的时候只有一个端点在变化位置，那么我们应该让区间尽量往左边“缩”，才能找到x后面紧挨的数，从而放弃掉那些更大的数
int search(int x) { while(l < r) { int mid = l + r >> 1; // 相当于(l + r) / 2 if(a[mid] >= x) r = mid; else l = mid + 1; } return a[l]; } int search2(int x) { while(l < r) { int mid = l + r + 1 >> 1; //这里+1是很有必要的 if(a[mid] <= x) l = mid; else r = mid - 1; } return a[l]; }具体怎么记忆呢 只需要想，当R = L + 1时，我们要使L == R来作为循环的结束 那么对于第一类，由向下取整，mid为L，此时L = mid + 1或者 R = mid 都能达到 L == R的状态 对于第二类，如果不写mid + l + 1 ，mid就依然取L，但是R = mid - 1就会跳过L == R的状态，或者L = mid 会进入无限循环
简单来说就是L + R 最终取到L L + R + 1 最终取到R
#include <algorithm> #include <iostream> #include <cstdio> using namespace std; const int MAXN = 100000 + 10; #define debug(x) cerr << #x << "=" << x << endl; #define lowbit(x) x&-x int n, a[MAXN], t[MAXN], h[MAXN]; void ins(int k, int pos) { while(pos <= n) { t[pos] += k; pos += lowbit(pos); } } int que(int pos) { int que_sum = 0; while(pos) { que_sum += t[pos]; pos -= lowbit(pos); } return que_sum; } int main() { scanf("%d", &n); for(int i=2; i<=n; i++) { scanf("%d", a + i); } for(int i=1; i<=n; i++) ins(1,i); for(int i=n; i>=1; i--) { int pos = a[i] + 1; int l = 1, r = n; int ans; while(l < r) { int mid = l + r >> 1; int tsum = que(mid); if(tsum >= pos) r = mid; else l = mid + 1; } h[i] = l; ins(-1, h[i]); } for(int i=1; i<=n; i++) { printf("%d\n", h[i]); } return 0; }