Camel and Oases
不难发现对于某个 V,一个点扩展出去的一段区间内所有点的区间相同。
故对于 v,\(\lfloor \frac{v}{2}\rfloor\),\(\lfloor\frac{\lfloor \frac{v}{2}\rfloor}{2}\rfloor\)...1,预处理 \(L_{i,j},R_{i,j}\) 表示 V=j 时 i 扩展最远的左右端点。
为方便处理,我们先排除初始为 V 时的区间。
设 \(DPL_{s},DPR_{s}\) 表示 V 的集合为 s,从1开始覆盖最右的点和从n开始覆盖最左的点。
这样对于初始的 \(l_i,r_i\) 只用判断是否前后缀能接上,设 x 为 V 时区间个数,复杂度 \(\Omicron(x2^{\log_2^v})\)
当 \(\log_2^v< x\) 时,所有点都用最大水量也覆盖不完 1-n 必定所有都为 Impossible,这样即可保证时间。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> kk;
#define mp make_pair
const int MAXN=2e5+5;
const int UP=20;
int c1,n,dpl[MAXN<<2],dpr[MAXN<<2],wz[MAXN],v,lev,up,L[UP][MAXN],R[UP][MAXN],len[UP];
kk cc[MAXN];
bool rs[MAXN];
int main(){
scanf("%d%d",&n,&v);
while(v>=0){
len[lev++]=v;v>>=1;
if(v==0){lev++;break;}
}up=1<<lev;
for(int i=1;i<=n;i++) scanf("%d",&wz[i]);
for(int now=0;now<lev;now++){
L[now][1]=1;
for(int i=2;i<=n;i++){
if(wz[i]-wz[i-1]<=len[now]) L[now][i]=L[now][i-1];else L[now][i]=i;
}
R[now][n]=n;
for(int i=n-1;i>=1;i--){
if(wz[i+1]-wz[i]<=len[now]) R[now][i]=R[now][i+1];else R[now][i]=i;
}
}
for(int i=1;i<=n;i++) cc[i]=mp(L[0][i],R[0][i]);
sort(cc+1,cc+1+n);c1=unique(cc+1,cc+1+n)-cc-1;
if(c1>lev){
for(int i=1;i<=n;i++) printf("Impossible\n");return 0;
}
for(int i=0;i<up;i+=2) dpr[i]=n+1;
for(int i=0;i<up;i+=2){
for(int j=1;j<lev;j++){
if((i>>j)&1) continue;
dpl[i|(1<<j)]=max(dpl[i|(1<<j)],R[j][dpl[i]+1]);
dpr[i|(1<<j)]=min(dpr[i|(1<<j)],L[j][dpr[i]-1]);
}
}
for(int i=1;i<=c1;i++){
for(int j=0;j<up;j+=2){
if(dpl[j]>=cc[i].first-1&&dpr[(up-2)^j]<=cc[i].second+1){
for(int k=cc[i].first;k<=cc[i].second;k++) rs[k]=1;
}
}
}
for(int i=1;i<=n;i++){
if(rs[i]) printf("Possible\n");else printf("Impossible\n");
}return 0;
}