Description

给定两个长为 $n$ 的由 $1$ 到 $k$ 组成的字符串 $A,B$。

有 $m$ 组互斥对 $(u,v)$ 表示字符 $u$ 和 $v$ 无法进行临项交换。

问 $A$ 是否能通过临项交换变为 $B$。

$1\le n\le10^5,1\le m\le5\times 10^4,1\le k\le 10^3$。

Solution

首先能够发现一个重要的性质：若 $(u,v)$ 为互斥对，则 $u,v$ 的相对位置关系固定。

这时就已经有一个 $O(nk)$ 的做法了，枚举每一种数再动态维护是否合法即可，本题时限 $4$ 秒足以通过。

但这太不优美了。

我们可以考虑从小到大枚举 $B$ 的每一位，判断 $A$ 中是否存在字符能够移到相应位置即可。

假设此时枚举到 $B_l$，存在两个位置 $r,r'$ 满足 $r<r',A_r=A_{r'}=B_l$。由于从小往大枚举，必定有 $l<r<r'$。

若 $A_{r'}$ 能够移动到 $l$，则$A_{r'}$ 必然能够移动到 $r$，也就相当于二者是能够互相到达的，所以将 $A_{r}$ 能够移动到 $l$ 保持不劣。

若是若是 $A_{r'}$ 无法移动到 $l$，则此时将 $A_{r}$ 移动到 $l$ 明显更优，因为不用经过 $[r,r']$。

因此由决策包容性可得：将 $A_r$ 移到 $l$ 要优于将 $A_{r'}$ 移到 $l$。

所以对于每一个 $B$ 中的位置 $l$，我们可以认为它是由 $A$ 中最近的对应字符移来的。

这里的最近不是指在原序列中距离最近，而是指在 $[1,l-1]$ 位置上的数都已经匹配后距离最近的数。

所以上述说法可以转化为：对于 $B$ 序列中的位置 $l$，假设它是值 $B_l$ 第 $x$ 次出现的位置，那么 $A$ 中相对应的位置就也应该是 $A$ 序列中值 $B_l$ 第 $x$ 次出现的位置。

这也就意味着，$A$ 序列中每个数要移到 $B$ 序列中的位置从一开始就是确定的，不妨设 $A_i$ 要移动到 $p_i$ 位置，用若干指针扫一遍就能把 $p$ 预处理出来了。

那么无法移动的情况很明显了：

• $j<i$
• $p_j>p_i$
• $(A_i,A_j)$ 是互斥对。

三维偏序，直接 cdq 就行了。

其中判断是否是互斥对可以用 bitset 优化，就不需要 $O(k)$ 枚举了。

总时间复杂度 $O(n\log n\dfrac{k}{w})$，其中 $w=64$，明显优于 $O(nk)$ 虽然好像也不是那么明显。

Code

#include<bits/stdc++.h>
#define INF 1e18
#define K 1005
#define N 100005
using namespace std;
struct node{
	int v,id;
}e[N];
int n,k,m,a[N],b[N],p[N],fl;
queue<int>q[K];
bitset<K>c[K],tmp;
bool cmp(node x,node y){
	return x.v<y.v;
}
void cdq(int l,int r){
	if(l==r) return;
	int mid=l+r>>1,j=l;
	cdq(l,mid),cdq(mid+1,r);
	sort(e+l,e+mid+1,cmp),sort(e+mid+1,e+r+1,cmp);
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&e[j].v<e[i].v) tmp[e[j].id]=1,j++;
		if((tmp&c[e[i].id]).count()) fl=0;
	}
	for(int i=l;i<=j;i++) tmp[e[i].id]=0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n>>k>>m,fl=1;
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		c[u][v]=1;
		c[v][u]=1;
	}
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) cin>>a[i],q[a[i]].push(i);
	for(int i=1;i<=n;i++){
		cin>>b[i],e[i].id=b[i];
        if(q[b[i]].empty()){
            cout<<"NIE";
            return 0;
        }
		e[i].v=-q[b[i]].front();
		q[b[i]].pop();
	}
	cdq(1,n);
	if(fl) cout<<"TAK";
	else cout<<"NIE";
	return 0;
}