定义两个长 的数组相似,当且仅当对于每一个区间 ,两个数组在该区间中最大值的位置相同。
给定 的排列 和一个长 且缺了 个值的数组 ,再给定一个大小为 的集合 。
次询问,每次给定一个整数 ,求能否将 以任意顺序填入 的空缺位置使得 和 相似。
保证 中元素两两不同。
,,。
首先观察到 和 相似当且仅当它们的笛卡尔树同构。
那么对于一个空缺的位置 ,它填入的数至少要 它子树的最大值 ,并且至少要 它父亲的值 。
现在我们来证明,只要所有空缺位置填入的数都 且 那么 就和 相似。
仅需证明互为祖先后代关系的空缺位置不会相互影响。
考虑满足 为 祖先的两个空缺位置 ,显然有 且 ,设 填入的数为 , 的为 ,那么 和 冲突当且仅当 。此时必有 ,也就是说,交换 和 也还是合法的。那么只要找到了一组满足填入的数 的填法,就一定可以通过交换来让它合法。
那么求出所有 ,问题变为:
给定 个区间 和一个大小为 的点的集合, 次询问,每次给定一个点 ,求 能否和区间一一匹配使得每个点都在对应区间内。
若 固定,则这个问题有一个经典贪心:
- 把区间按照 从小到大排序,把点也从小到大排序;
- 从小到大枚举位置 :
- 加入 的区间;
- 若存在点 ,则把它和当前已经加入的 最小的区间匹配;
- 若每次都能找到可以匹配的区间则有解,否则无解。
考虑魔改一下这个贪心,直接在 上跑,若有点找不到与之匹配的区间则无解,否则一定有一个区间失配,设该区间为 。注意到这个贪心本质上是尽量让剩下的区间 更大,所以 一定要 。
同理,反过来做一遍这个贪心即可得出一个 表示 一定要 。
现在我们得知 是必要条件,考虑证明它是充分的。
注意到这是一个完美匹配问题,考虑用 Hall 定理描述其有解性。这类问题有一个结论:
存在大小为 的匹配当且仅当:
- 把值域离散化到 后,对于所有区间 ,被 完全包含的区间个数 ;
那么设 表示被 完全包含的区间个数, 表示 中点的个数,。
若存在 则就算加入点 也不合法,一定无解。
若 则不用管,设 ,则仅需证明
必要条件那里已经证明了 ,现在仅需证明 。
先来证明 , 同理。
对于一个 的 ,必然有一个区间 被它包含且无法被 内点匹配,那么贪心肯定能找到 ,所以 必然 。
那么证完了, 是充要条件。
直接模拟即可,时间复杂度 。
代码如下:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
const int S=300005,BS=25;
const int inf=1e8;
struct node
{
int l,r;
};
int n,q,a[S],b[S];
int m,idx[S],c[S];
int mlog[S],mx[S][BS];
int cnt,pos[S],rpos[S],ls[S],rs[S];
int lb[S],rb[S];
node sg[S];
bool vis[S];
int L,R;
inline int quemx(int l,int r)
{
int k=mlog[r-l+1];
int x=mx[l][k],y=mx[r-(1<<k)+1][k];
return a[x]>a[y]?x:y;
}
inline void initmx()
{
mlog[0]=-1;
for(int i=1;i<=n;i++) mlog[i]=mlog[i>>1]+1;
for(int i=1;i<=n;i++) mx[i][0]=i;
for(int j=1;j<=mlog[n];j++)
{
for(int i=1;i<=n-(1<<j)+1;i++)
{
int x=mx[i][j-1],y=mx[i+(1<<j-1)][j-1];
mx[i][j]=a[x]>a[y]?x:y;
}
}
}
int built(int l,int r)
{
int u=++cnt;
int rt=quemx(l,r);
rpos[pos[u]=rt]=u;
ls[u]=rt==l?0:built(l,rt-1);
rs[u]=rt==r?0:built(rt+1,r);
return u;
}
void dfs(int u,int x)
{
rb[u]=x,lb[u]=0;
if(b[pos[u]]!=0) x=min(x,b[pos[u]]);
if(ls[u]!=0) dfs(ls[u],x),lb[u]=max(lb[u],max(lb[ls[u]],b[pos[ls[u]]]));
if(rs[u]!=0) dfs(rs[u],x),lb[u]=max(lb[u],max(lb[rs[u]],b[pos[rs[u]]]));
// printf("%d(%d)[%d %d]: %d %d\n",u,pos[u],lb[u],rb[u],ls[u],rs[u]);
}
inline void getLR()
{
for(int i=1;i<=n;i++)
{
if(b[i]==0) continue;
if(b[i]<lb[rpos[i]]||b[i]>rb[rpos[i]]) return L=inf,R=-inf,void();
}
for(int i=1;i<=m;i++) sg[i]=(node){lb[idx[i]],rb[idx[i]]};
// for(int i=1;i<=m;i++) printf("[%d %d]\n",sg[i].l,sg[i].r);
// calc R
for(int i=1;i<=m;i++) vis[i]=false;
sort(sg+1,sg+m+1,[&](node x,node y){return x.l<y.l;});
sort(c+1,c+m,[&](int x,int y){return x<y;});
priority_queue<pair<int,int> > q;
for(int i=1,j=1;i<=m-1;i++)
{
while(j<=m&&sg[j].l<=c[i]) q.push(make_pair(-sg[j].r,j)),j++;
while(!q.empty()&&-q.top().first<c[i]) q.pop();
if(q.empty()) return L=inf,R=-inf,void();
vis[q.top().second]=true;
q.pop();
}
for(int i=1;i<=m;i++) if(!vis[i]) R=sg[i].r;
// calc L
for(int i=1;i<=m;i++) vis[i]=false;
sort(sg+1,sg+m+1,[&](node x,node y){return x.r>y.r;});
sort(c+1,c+m,[&](int x,int y){return x>y;});
while(!q.empty()) q.pop();
for(int i=1,j=1;i<=m-1;i++)
{
while(j<=m&&sg[j].r>=c[i]) q.push(make_pair(sg[j].l,j)),j++;
while(!q.empty()&&q.top().first>c[i]) q.pop();
if(q.empty()) return L=inf,R=-inf,void();
vis[q.top().second]=true;
q.pop();
}
for(int i=1;i<=m;i++) if(!vis[i]) L=sg[i].l;
}
inline void slove()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
m=0;
for(int i=1;i<=n;i++) if(b[i]==0) idx[++m]=i;
for(int i=1;i<=m-1;i++) scanf("%d",&c[i]);
initmx();
cnt=0;
built(1,n);
for(int i=1;i<=m;i++) idx[i]=rpos[idx[i]]/*,printf(">> %d\n",idx[i])*/;
dfs(1,inf);
for(int i=1;i<=cnt;i++) lb[i]++,rb[i]--;
getLR();
// printf("%d %d\n",L,R);
while(q-->0)
{
int x;
scanf("%d",&x);
puts(L<=x&&x<=R?"YES":"NO");
}
}
int main()
{
int T;
scanf("%d",&T);
while(T-->0) slove();
return 0;
}
/*
1
4 2
4 1 3 2
0 5 3 0
2
4
6
*/