【雪地】

【雪地】

WOJ地址

s e t set set

先预处理出一次滑行i的鞋子最少需要的厚度是多少， O ( 1 ) O(1) O(1)查询即可。

考虑将雪地高度从小到大加入，每次把当前所在的区间切成两个区间，查询一下最大的区间，与原来的取 m i n min min即可。

为什么要用 s e t set set？
因为 s e t set set自动从小到大排序，且支持插入和删除。

(内含一个暴力程序)

#include<bits/stdc++.h>
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f==1?x:-x;
}
const int N=1e5+5;
int n,m,a[N],mx=0;
int check(int s,int d){int f=0;for(int i=1;i<=n;i++){if(a[i]>s)f++;else f=0;if(f>=d)return 0;}return 1;
}
void work_1(){for(int i=1;i<=n;i++){a[i]=read();mx=(a[i]>mx)?a[i]:mx;}while(m--){int s,d;s=read();d=read();if(s>=mx){printf("1\n");continue;}printf("%d\n",check(s,d));}
}
struct node{int hei,pos;
}b[N];
inline bool Sort(const node &x,const node &y){return x.hei<y.hei;
}
int d[N],r[N];//右端点的左端点
set<int>sr;//右端点
multiset<int>sl;//slen  区间长度
void work_2(){memset(d,0x3f,sizeof(d));for(int i=1;i<=n;i++){b[i].hei=read();b[i].pos=i;}sort(b+1,b+n+1,Sort);r[n]=1;d[n-1]=0;sr.insert(n);sl.insert(1-n);//用负数变成从大到小排序for(int i=1;i<=n;i++){int h=b[i].hei,x=b[i].pos;int v=*sr.lower_bound(x);//找到所在区间int u=r[v];r[v]=x;r[x]=u;//拆成两个区间sr.insert(x);//插入新的右端点sl.erase(sl.find(u-v));//删除原来长度sl.insert(u-x);sl.insert(x-v);//插入新长度u=*sl.begin();u=-u;//找最大d[u]=min(d[u],h);//更新答案}for(int i=1;i<n;i++)if(d[i]==0x3f3f3f3f)d[i]=d[i-1];//有些d[i]可能没算到，更新一下while(m--){int s,k;s=read();k=read();if(s>=d[k])printf("1\n");//O(1)查询else printf("0\n");}
}
int main(){n=read();m=read();if(n<=1000&&m<=1000)work_1();//暴力else work_2();//正解return 0;
}

【雪地】

【雪地】

WOJ地址

s e t set set

先预处理出一次滑行i的鞋子最少需要的厚度是多少， O ( 1 ) O(1) O(1)查询即可。

考虑将雪地高度从小到大加入，每次把当前所在的区间切成两个区间，查询一下最大的区间，与原来的取 m i n min min即可。

为什么要用 s e t set set？
因为 s e t set set自动从小到大排序，且支持插入和删除。

(内含一个暴力程序)

#include<bits/stdc++.h>
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f==1?x:-x;
}
const int N=1e5+5;
int n,m,a[N],mx=0;
int check(int s,int d){int f=0;for(int i=1;i<=n;i++){if(a[i]>s)f++;else f=0;if(f>=d)return 0;}return 1;
}
void work_1(){for(int i=1;i<=n;i++){a[i]=read();mx=(a[i]>mx)?a[i]:mx;}while(m--){int s,d;s=read();d=read();if(s>=mx){printf("1\n");continue;}printf("%d\n",check(s,d));}
}
struct node{int hei,pos;
}b[N];
inline bool Sort(const node &x,const node &y){return x.hei<y.hei;
}
int d[N],r[N];//右端点的左端点
set<int>sr;//右端点
multiset<int>sl;//slen  区间长度
void work_2(){memset(d,0x3f,sizeof(d));for(int i=1;i<=n;i++){b[i].hei=read();b[i].pos=i;}sort(b+1,b+n+1,Sort);r[n]=1;d[n-1]=0;sr.insert(n);sl.insert(1-n);//用负数变成从大到小排序for(int i=1;i<=n;i++){int h=b[i].hei,x=b[i].pos;int v=*sr.lower_bound(x);//找到所在区间int u=r[v];r[v]=x;r[x]=u;//拆成两个区间sr.insert(x);//插入新的右端点sl.erase(sl.find(u-v));//删除原来长度sl.insert(u-x);sl.insert(x-v);//插入新长度u=*sl.begin();u=-u;//找最大d[u]=min(d[u],h);//更新答案}for(int i=1;i<n;i++)if(d[i]==0x3f3f3f3f)d[i]=d[i-1];//有些d[i]可能没算到，更新一下while(m--){int s,k;s=read();k=read();if(s>=d[k])printf("1\n");//O(1)查询else printf("0\n");}
}
int main(){n=read();m=read();if(n<=1000&&m<=1000)work_1();//暴力else work_2();//正解return 0;
}