CF1718D Permutation for Burenka 做题记录

定义两个长 $n$ 的数组相似，当且仅当对于每一个区间 $[l,r]$，两个数组在该区间中最大值的位置相同。

给定 $n$ 的排列 $p$ 和一个长 $n$ 且缺了 $k$ 个值的数组 $a$，再给定一个大小为 $k-1$ 的集合 $S$。

$q$ 次询问，每次给定一个整数 $d$，求能否将 $S\cup\{d\}$ 以任意顺序填入 $a$ 的空缺位置使得 $a$ 和 $p$ 相似。

保证 $a,S,d$ 中元素两两不同。

$1\le n,q\le 3\times 10^5$，$2\le k\le n$，$1\le a_i,S_i,d\le 10^6$。

首先观察到 $a$ 和 $p$ 相似当且仅当它们的笛卡尔树同构。

那么对于一个空缺的位置 $u$，它填入的数至少要 $>$ 它子树的最大值 $mx_u$，并且至少要 $<$ 它父亲的值 $vf_u$。

现在我们来证明，只要所有空缺位置填入的数都 $> mx_u$ 且 $<vf_u$ 那么 $a$ 就和 $p$ 相似。

仅需证明互为祖先后代关系的空缺位置不会相互影响。

考虑满足 $x$ 为 $y$ 祖先的两个空缺位置 $x,y$，显然有 $mx_x\ge mx_y$ 且 $vf_x\ge vf_y$，设 $x$ 填入的数为 $v_x$，$y$ 的为 $v_y$，那么 $v_x$ 和 $v_y$ 冲突当且仅当 $v_x<v_y$。此时必有 $mx_y\le mx_x<v_x<v_y<vf_y\le vf_x$，也就是说，交换 $v_x$ 和 $v_y$ 也还是合法的。那么只要找到了一组满足填入的数 $\in[mx_u+1,vf_u-1]$ 的填法，就一定可以通过交换来让它合法。

那么求出所有 $[mx_u+1,vf_u-1]$，问题变为：

给定 $k$ 个区间 $[l,r]$ 和一个大小为 $k-1$ 的点的集合，$q$ 次询问，每次给定一个点 $d$，求 $S\cup\{d\}$ 能否和区间一一匹配使得每个点都在对应区间内。

若 $S\cup\{d\}$ 固定，则这个问题有一个经典贪心：

• 把区间按照 $l$ 从小到大排序，把点也从小到大排序；
• 从小到大枚举位置 $p$：
  • 加入 $l=p$ 的区间；
  • 若存在点 $p$，则把它和当前已经加入的 $r$ 最小的区间匹配；
• 若每次都能找到可以匹配的区间则有解，否则无解。

考虑魔改一下这个贪心，直接在 $S$ 上跑，若有点找不到与之匹配的区间则无解，否则一定有一个区间失配，设该区间为 $[lb,rb]$。注意到这个贪心本质上是尽量让剩下的区间 $r$ 更大，所以 $d$ 一定要 $\le rb$。

同理，反过来做一遍这个贪心即可得出一个 $lb$ 表示 $d$ 一定要 $\ge lb$。

现在我们得知 $d\in[lb,rb]$ 是必要条件，考虑证明它是充分的。

注意到这是一个完美匹配问题，考虑用 Hall 定理描述其有解性。这类问题有一个结论：

存在大小为 $k$ 的匹配当且仅当：

• 把值域离散化到 $[1,k]$ 后，对于所有区间 $[l,r]$，被 $[l,r]$ 完全包含的区间个数 $\le r-l+1$；

那么设 $f(l,r)$ 表示被 $[l,r]$ 完全包含的区间个数，$g(l,r)$ 表示 $[l,r]$ 中点的个数，$h(l,r)=f(l,r)-g(l,r)$。

若存在 $h(l,r)>1$ 则就算加入点 $d$ 也不合法，一定无解。

若 $h(l,r)\le 0$ 则不用管，设 $[L,R]=\cap_{h(l,r)=1}[l,r]$，则仅需证明 $[L,R]=[lb,rb]$

必要条件那里已经证明了 $lb\le L,rb\ge R$，现在仅需证明 $lb\ge L,rb\le R$。

先来证明 $rb\le R$，$lb\ge L$ 同理。

对于一个 $h(l,r)=1$ 的 $[l,r]$，必然有一个区间 $i$ 被它包含且无法被 $[l,r]$ 内点匹配，那么贪心肯定能找到 $r_i$，所以 $rb$ 必然 $\le R$。

那么证完了，$d\in[lb,rb]$ 是充要条件。

直接模拟即可，时间复杂度 $O(n\log n)$。

代码如下：

#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
*/