HDU 3193-Find the hotel (RMQ)

题目传送门
题意：找到所有满足（不存在比该酒店价格和距离都低的其他酒店）这样的酒店。

思路：即价格大于等于它的酒店不用考虑，只用考虑价格比他小的酒店当中是否距离最小的那个比它的距离大。若存在一个即该酒店满足。最后排序。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
#define PII pair<int,int>
struct node{
	int p,d;
}a[N];
int b[N],dp[N][22],n;
void rmq(){ //预处理 rmq 
	for(int j=1;(1<<j)<=1e4;j++)
		for(int i=0;i+(1<<j)-1<=1e4;i++)
				dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
int fun(int l,int r){
	int len=r-l+1,k=0;
	while((1<<k)*2<len) k++;
	return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
bool cmp(PII a,PII b){
	return a.first==b.first?a.second<b.second:a.first<b.first;
}
int main(){
	while(~scanf("%d",&n)){
		memset(b,0x3f,sizeof b);//初始化 
	vector<PII >ans; 
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i].p,&a[i].d);
	 a[i].p++,a[i].d++;//存在值为0的情况加1便于处理 
	 b[a[i].p]=min(b[a[i].p],a[i].d);//记录相同价格的最小距离. 
	}
	  for(int i=0;i<N;i++)
			dp[i][0]=b[i];//初始化 
	rmq();
	for(int i=1;i<=n;i++)
	{
		int tmp=fun(0,a[i].p-1);//必须从0开始,若为1开始当 a[i].p=1时 a[i].p-1=0 则是L=1,R=0发生错误. 
		if(tmp>=a[i].d)//已知价格大于等于a[i].p的都满足条件,只要价格比它小的酒店距离都大于等于它就可以 
			ans.push_back({a[i].p,a[i].d}); 
	}
	printf("%d\n",ans.size());
	sort(ans.begin(),ans.end(),cmp);
	for(auto i:ans) printf("%d %d\n",i.first-1,i.second-1);//还原 
	}
	return 0;
}