CF1718D Permutation for Burenka 做题记录

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

给定 nn 的排列 pp 和一个长 nn 且缺了 kk 个值的数组 aa,再给定一个大小为 k1k-1 的集合 SS

qq 次询问,每次给定一个整数 dd,求能否将 S{d}S\cup\{d\} 以任意顺序填入 aa 的空缺位置使得 aapp 相似。

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

1n,q3×1051\le n,q\le 3\times 10^52kn2\le k\le n1ai,Si,d1061\le a_i,S_i,d\le 10^6

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

那么对于一个空缺的位置 uu,它填入的数至少要 >> 它子树的最大值 mxumx_u,并且至少要 << 它父亲的值 vfuvf_u

现在我们来证明,只要所有空缺位置填入的数都 >mxu> mx_u<vfu<vf_u 那么 aa 就和 pp 相似。

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

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

那么求出所有 [mxu+1,vfu1][mx_u+1,vf_u-1],问题变为:

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

S{d}S\cup\{d\} 固定,则这个问题有一个经典贪心:

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

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

同理,反过来做一遍这个贪心即可得出一个 lblb 表示 dd 一定要 lb\ge lb

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

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

存在大小为 kk 的匹配当且仅当:

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

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

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

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

必要条件那里已经证明了 lbL,rbRlb\le L,rb\ge R,现在仅需证明 lbL,rbRlb\ge L,rb\le R

先来证明 rbRrb\le RlbLlb\ge L 同理。

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

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

直接模拟即可,时间复杂度 O(nlogn)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
*/