[基础] 学习笔记

1. 重载运算符

struct node
{
	int x;
	bool operator < (const node & a) const
	{
		return x > a.x; // 从小到大
	}
};
priority_queue< node > q;

struct cmp
{
	  bool operator()(const int & a, const int & b)
	  {
			...
	  }
};
priority_queue< int, vector<int>, cmp >  q;

2. 二分

在单调递增序列 \(a\) 中查找 第一个 \(\geqslant x\) 的数，即 \(x\) 或 \(x\) 的后继。

while (l < r)
{
	int mid = (l + r) >> 1;
	if (a[mid] >= x) r = mid;
	else l = mid + 1;
}
return a[l];

在单调递增序列 \(a\) 中查找 第一个 \(\leqslant x\) 的数，即 \(x\) 或 \(x\) 的前驱。

while (l < r)
{
	int mid = (l + r + 1) >> 1;
	if (a[mid] <= x) l = mid;
	else r = mid - 1;
}
return a[l];