lower_bound 和 upper_bound函数

一、用法

1.对于递增序列

当容器中的元素按照递增的顺序存储时，lower_bound函数返回容器中第一个大于等于目标值的位置，upper_bound函数返回容器中第一个大于目标值的位置。若容器中的元素都比目标值小则返回最后一个元素的下一个位置。

对于vector和数组，若想用lower_bound获取下标：

对于vector: int pos = lower_bound(v.begin(),v.end(),x)-v.begin();

对于数组： int pos = lower_bound(a,a+n,x)-a;

2.对于递减序列

那么接下来考虑，如果容器中元素是递减的如何查找呢？

可以利用仿函数greater<date_type>()去重新定义比较规则。这样的话对于lowerbound()查找的是容器中第一个小于等于目标值的元素的位置，而upper_bound()查找的是容器中第一个小于目标值的元素的位置就。如果容器中的元素都比目标值大则返回最后一个元素的下一个位置。

set<int,greater<int>>s;
auto it = s.lower_bound(x);//返回第一个小于x的元素的迭代器

二、相关常用操作

1.prev 和 next

1.1 prev反向

先建立一个容器，插入1~10

set<int>s;
for(int i = 1;i<=10;i++)
    s.insert(i);

对于prev：

若用lower_bound，可以或与大于等于目标的第一个数，比如：

cout<<*s.lower_bound(5)<<endl;

输出应该是大于等于5的第一个数，那么就是5

如果用prev的话：

cout<<*prev(s.lower_bound(5))<<endl;

prev起到反向作用，一开始的大于等于变成了小于，那么会找到4

1.2 nxet位移

还是以上述set容器为例

auto it = s.begin();
cout<<*next(it,2)<<endl;

这里会输出3，因为相当于begin后面两个位置的数。

如果参数是负数，就会往前找：

it = --s.end();
cout<<*next(it,-3)<<endl;

会去找末尾往前三个位置，那就是7了。

三、例题

[abc273_d](D - LRUD Instructions (atcoder.jp))

题意：

你有一个\(n\times m\) 的矩阵，矩阵上有 \(N\) 个障碍物，现在给你 \(Q\)次询问，问向 \(R_i\) 的方向走 \(C_i\)步到哪里了。前一步能影响后一步，障碍物不能越过，不能走出边界。

思路：

首先很明显直接模拟肯定T，那么我们对于一个点需要快速知道离每个方向它最近的的一个障碍物的位置，可以用\(map<ll,set<ll>>\)来快速查找。因为数据范围\(1e9\)，需要离散化一下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,x,y;
map<ll,set<ll>>dx,dy;
int main()
{
	cin>>n>>m>>x>>y;
	int N;
	cin>>N;
	for(int i = 1;i<=N;i++)
	{
		ll xx,yy;
		cin>>xx>>yy;
		dx[xx].insert(yy);
		dy[yy].insert(xx);
	}

	for(auto &i:dx)
	{
		i.second.insert(0);
		i.second.insert(m+1);
	}
	for(auto &i:dy)
	{
		i.second.insert(0);
		i.second.insert(n+1);
	}
	
	int q;
	cin>>q;
	for(int i = 1;i<=q;i++)
	{
		char op;
		ll k;
		cin>>op>>k;
		if(op=='L')
		{
			ll nxt_y = y-k;
			if(dx.find(x)==dx.end())//如果在x这一行都没有障碍物那么就直接走，只要不越界
				y = max(nxt_y,1ll);
			else
			{
				auto it = dx[x].lower_bound(y);//找到>=y的第一个
				it = prev(it);
                //prev反向，那么找到<y的第一个(因为我们要向左走)那么*it是第一个不能到达的地方,最多能走到*it+1
				y = max(*it+1,nxt_y);
			}
		}
		else if(op=='R')
		{
			ll nxt_y = y+k;
			if(dx.find(x)==dx.end())
				y = min(nxt_y,(ll)m);
			else
			{

				auto it = dx[x].lower_bound(y);
				y = min(*it-1,nxt_y);
			}
		}
		else if(op=='U')
		{
			ll nxt_x = x-k;
			if(dy.find(y)==dy.end())
				x = max(nxt_x,1ll);
			else
			{
				auto it = dy[y].lower_bound(x);
				it = prev(it);
				x = max(*it+1,nxt_x);
			}
		}
		else
		{
			ll nxt_x = x+k;
			if(dy.find(y)==dy.end())
				x = min(nxt_x,(ll)n);
			else
			{
				auto it = dy[y].lower_bound(x);
				x = min(*it-1,nxt_x);
			}
		}
		cout<<x<<" "<<y<<endl;
	}
	return 0;
}