题解：CF1887D Split

· · 题解

因为我很喜欢暴力数据结构，所以我使用分块通过了此题。

思路

容易发现只要决策点左边的 \max 小于右边的 \min 就合法。

考虑分块，散块暴力，考虑怎么处理整块的答案。

设询问区间为 [l,r]，当前块区间为 [L,R]，对于一个决策点 p\in[L,R)，设 mx=\max\limits_{i=L}^{p}a_i,mi=\min\limits_{i=p+1}^{R}a_i,MX=\max\limits_{i=l}^{L-1}a_i,MI=\min\limits_{i=R+1}^{r}a_i，那么发现只要 [mx,mi] 和 [MX,MI] 有交就合法，考虑对每个块求出 [mx,mi]，相当于对 [mx,mi] 区间加一，直接差分前缀和即可。

注意一下这题卡空间所以要逐块处理。

代码

#include<bits/stdc++.h>
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<23],*p1=buf,*p2=buf;
int read(){int p=0,flg=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-') flg=-1;c=getchar();}while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}return p*flg;}
int n,m,a[300010],b[300010],ans[300010],B,pos[300010],L[1010],R[1010],mx[1010],mi[1010],pmx[300010],smx[300010],pmi[300010],smi[300010],bmx[1010][1010],bmi[1010][1010],sum[300010];struct Q{int l,r;}q[300010];
void build(){
    B=sqrt(12*n);for(int i=1;i<=n;i++) pos[i]=(i-1)/B+1;for(int i=1;i<=pos[n];i++){
        L[i]=(i-1)*B+1,R[i]=min(n,i*B);mx[i]=0;mi[i]=n+1;for(int j=L[i];j<=R[i];j++) mx[i]=max(mx[i],a[j]),pmx[j]=mx[i],mi[i]=min(mi[i],a[j]),pmi[j]=mi[i];
        mx[i]=0;mi[i]=n+1;for(int j=R[i];j>=L[i];j--) mx[i]=max(mx[i],a[j]),smx[j]=mx[i],mi[i]=min(mi[i],a[j]),smi[j]=mi[i];
    }for(int i=1;i<=pos[n];i++){bmx[i][i]=mx[i];bmi[i][i]=mi[i];for(int j=i+1;j<=pos[n];j++) bmx[i][j]=max(bmx[i][j-1],mx[j]),bmi[i][j]=min(bmi[i][j-1],mi[j]);for(int j=0;j<i;j++) bmi[i][j]=n+1;}
}
int main(){
    n=read();for(int i=1;i<=n;i++) a[i]=read();m=read();for(int i=1;i<=m;i++) q[i]={read(),read()};
    build();for(int i=1;i<=m;i++){
        int l=q[i].l,r=q[i].r;if(pos[r]-pos[l]+1<=2){b[r]=a[r];for(int j=r-1;j>=l;j--) b[j]=min(b[j+1],a[j]);for(int j=l,pre=0;j<r;j++){pre=max(pre,a[j]);if(pre<b[j+1]) ans[i]|=1;}continue;}
        for(int j=l,pre=0;j<=R[pos[l]];j++){pre=max(pre,a[j]);if(pre<min({bmi[pos[l]+1][pos[r]-1],pmi[r],j^R[pos[l]]?smi[j+1]:n+1})) ans[i]|=1;}
        for(int j=r,suf=n+1;j>=L[pos[r]];j--){suf=min(suf,a[j]);if(suf>max({bmx[pos[l]+1][pos[r]-1],smx[l],j^L[pos[r]]?pmx[j-1]:0})) ans[i]|=1;}
    }for(int i=1;i<=pos[n];i++){
        memset(sum,0,sizeof(sum));for(int j=L[i];j<=R[i];j++){int l=pmx[j],r=j^R[i]?smi[j+1]:n+1;if(l>r) continue;sum[l]++;sum[r+1]--;}
        int now=0;for(int j=1;j<=n+2;j++) now+=sum[j],sum[j]=sum[j-1]+now;
        for(int j=1;j<=m;j++){int l=q[j].l,r=q[j].r;if(i<=pos[l]||pos[r]<=i) continue;int ql=max(smx[l],bmx[pos[l]+1][i-1]),qr=min(bmi[i+1][pos[r]-1],pmi[r]);if(ql<=qr&&sum[qr]-sum[ql-1]) ans[j]|=1;}
    }for(int i=1;i<=m;i++) cout<<(ans[i]?"Yes\n":"No\n");
    return 0;
}