P4269 题解
这里提供一种略微暴力的方法。
如这篇题解所说，当我们把靴子按高度降序排序时，后面的靴子能走的地方肯定不比前面的靴子的多。当有两个能走的地方之间的距离（不包含两边）大于等于这双靴子的最大步长且这两个能走的地方之间没有其他的能走的地方，这双靴子就不能穿了。
详见代码。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,b,a[500001],ans[500001];
struct node{
int id;//id表示排序前这双靴子的序号（因为要按原顺序输出）
int s,d;
}q[500001];
vector<int> v;//v用来存目前能走的地方
bool cmp(node a,node b){//把靴子按高度降序排序
return a.s>b.s;
}
int main(){
cin>>n>>b;
for(int i=1;i<=n;i++){
cin>>a[i];
v.push_back(i);//一开始我们不知道哪些地方不能走，就都放进去
}
for(int i=1;i<=b;i++){
cin>>q[i].s>>q[i].d;
q[i].id=i;
}
sort(q+1,q+b+1,cmp);
for(int i=1;i<=b;i++){
vector<int> now;//now用来存排序后第i双靴子新增的不能走的地方
bool check=true;//check为true表示排序后第i双靴子能穿过雪地，为false表示不能
for(int j=0;j<v.size();j++){
if(a[v[j]]>q[i].s){
now.push_back(v[j]);
}
}
for(int j=0;j<now.size();j++){//挨个把新增的不能走的地方从v中删除
v.erase(lower_bound(v.begin(),v.end(),now[j]));//因为v有序，所以可以二分
}
for(int j=0;j<v.size()-1;j++){
if(v[j+1]-v[j]-1>=q[i].d){
check=false;
break;
}
}
if(check==true){
ans[q[i].id]=1;
}else{
ans[q[i].id]=0;
}
}
for(int i=1;i<=b;i++){
cout<<ans[i]<<endl;
}
return 0;
}因为做法有些过于暴力，且使用了大量的 STL，所以在不开 -O2 优化的情况下是会时间超限的。但是当开启 -O2 优化时，是可以勉强卡过的。记录