CF1887D Split
樱雪喵
·
·
题解
Description
定义一个序列是好的，当且仅当它存在某种划分成左右两部分的方案，使左半部分的最大值严格小于右半部分的最小值。
现给出长度为 n 的序列 a，保证 a 是一个 1\sim n 的排列。
$n,q\le 3\times 10^5$。
## Solution
考虑对于一个确定的序列怎么搞。我们枚举一个值域分界点 $i$，把 $\le i$ 的分在一边，$>i$ 的分在另一边，判断它们是否恰好是原序列的某种划分。
然而这个东西没有单调性，从其它角度优化这个过程。
我们对于每个**下标** $i$，不考虑具体的询问，而是考虑能使 $a_i$ 成为合法的**值域**分界点的区间 $[l,r]$ 中 $l,r$ 的范围。
首先，$a_i$ 一定在左半部分，且是左半部分的最大值。那么令 $x$ 为 $i$ 向左找第一个 $a_x>a_i$ 的位置。则左端点有限制 $x< l\le i$。
右半部分需满足全部值大于 $a_i$。那么令 $y$ 为 $i$ 右侧第一个 $a_y>a_i$ 的位置，有限制 $r\ge y$。同时令 $z$ 为 $y$ 右侧第一个 $a_z<a_i$ 的位置，有限制 $y\le r < z$。
把询问 $[l,r]$ 看作点的坐标，这是一个矩阵加单点查询问题，使用树状数组 + 扫描线维护。
```cpp
const int N=3e5+5;
int n,m,a[N],pos[N],ans[N],tot;
struct node {int tp,l,r,x,k,y,id;}q[N<<2];
set<int> ls,rs;
il bool cmp(node x,node y)
{
if(x.x!=y.x) return x.x<y.x;
else return x.tp<y.tp;
}
struct BIT
{
int tr[N];
il void modify(int x,int k) {for(;x<=n;x+=x&(-x)) tr[x]+=k;}
il void add(int l,int r,int k) {modify(l,k),modify(r+1,-k);}
il int query(int x) {int res=0;for(;x;x-=x&(-x)) res+=tr[x];return res;}
}tr;
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read(),pos[a[i]]=i,rs.insert(i);
for(int I=1;I<=n;I++)
{
int i=pos[I];
rs.erase(i);
auto itx=rs.lower_bound(i),ity=rs.upper_bound(i);
int x=(itx==rs.begin()||itx==rs.end())?0:*prev(itx);
int y=(ity==rs.end())?n+1:*ity;
auto itz=ls.upper_bound(y);
int z=(itz==ls.end())?n+1:*itz;
q[++tot]={1,x+1,i,y,1,0,0};
q[++tot]={1,x+1,i,z,-1,0,0};
ls.insert(i);
}
m=read();
for(int i=1;i<=m;i++)
{
int l=read(),r=read();
q[++tot]={2,0,0,r,0,l,i};
}
sort(q+1,q+tot+1,cmp);
for(int i=1;i<=tot;i++)
{
if(q[i].tp==1) tr.add(q[i].l,q[i].r,q[i].k);
else ans[q[i].id]=tr.query(q[i].y);
}
for(int i=1;i<=m;i++) printf(ans[i]?"Yes\n":"No\n");
return 0;
}
```