二分

FFFTTTT

1
2
3
4
5
6
7
8
9
10
template <typename T, typename M>
T get_first_match(T lo, T hi, M match) {
    while (lo <= hi) {
        T mid = lo + (hi - lo) / 2;
        if(match(mid)) hi = mid - 1;
        else lo = mid + 1;
    }
    return lo;
}
//FFFF...FFTTTT  ->  [lo, hi]闭区间内，寻找第一个match的值

TTTTFFFFF

1
2
3
4
5
6
7
8
9
10
template <typename T, typename M>
T bs(T lo, T hi, M match) {
  while (lo <= hi) {
    T mid = lo + (hi - lo) / 2;
    if (match(mid)) lo = mid + 1;
    else hi = mid - 1;
  }
  return hi;
}
//TTTT..TFFFF  ->  寻找最后一个符合的值

整数向上取整

1
[a / b] = (a + b - 1) / b

单调性枚举

单调性递增枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename M, typename I, typename R, typename U>
void increaseEnumerate(int s, int e, const M& match,
const I& insert, const R& remove, const U& update){
	for (int l = s, r = s; l <= e; ) {
	    if (l < r && match(l, r - 1)) {
	        update(l, r - 2);
	        remove(l ++, r);
	    } else if (r <= e) {
	        insert(l, r++);
	    } else {
	        update(l, r - 1);
	        remove(l ++, r);
	    }
	}
}