Description

给定正整数 $m$，定义基本集合为大小为 $3$，元素在 $1\sim m$ 内的集合。例如：给定 $m=4$，则集合 $\{1,2,3\}$ 与集合 $\{2,3,4\}$ 都是基本集合。

定义集合序列为由基本集合构成的序列，例如，$A=[\{1,2,3\},\{2,3,4\}]$ 是一个集合序列，其中 $A[1]=\{1,2,3\}$，$A[2]=\{2,3,4\}$ 都是基本集合。

对于一个 $1\sim m$ 的排列 $p[1],p[2],\dots,p[m]$ 与集合 $S\subseteq \{1,2,\dots,m\}$，定义 $f_p(S)$ 为将 $S$ 内每一个元素 $x$ 置换为 $p[x]$ 后所得到的集合，即 $f_p(S)=\{p[x]|x\in S\}$。

对于两个长度为 $k$ 的集合序列 $A,B$，定义 $A$ 和 $B$ 等价当且仅当存在一个 $1\sim m$ 的排列 $p$，使得 $A$ 置换排列 $p$ 后得到 $B$，即对于所有 $1\leq i\leq k$，$f_p(A[i])=B[i]$。

给定两个长度为 $n$ 的集合序列 $A,B$，有 $q$ 次询问。每次小 S 会询问小 Y，在给定 $l,r$ 的情况下，求出有多少排列能使集合序列 $[A[l],A[l+1],\dots,A[r]]$ 与集合序列 $[B[l],B[l+1],\dots,B[r]]$ 等价。

---

Solution

• 若无特殊说明，下文中的匹配均指两个值之间的映射

4 pts

puts("6");

---

16 pts

注意到 $m$ 非常小，暴力枚举排列并暴力判断其对于每个询问区间是否合法即可，复杂度 $O(m!\cdot nq)$。

---

28 pts

我们发现 $m$ 的限制不变，但 $n$ 和 $q$ 变大了，于是考虑枚举排列后加速判断询问区间合法的过程。

询问区间合法等价于区间内每个位置的限制均合法，考虑计数区间内合法的位置，若其数量等于询问区间的长度，则区间合法。做一遍前缀和即可 $O(1)$ 单次判断，总复杂度 $O(m!\cdot(n+q))$。

---

64 pts

我们记 $posa[x]$ 表示值 $x$ 在 $A$ 中出现位置的集合， $posb[x]$ 表示值 $x$ 在 $B$ 中出现位置的集合，一个排列 $p$ 合法当且仅当其满足 $\forall \ i,posa[i]=posb[p_i]$。

注意到只要两个数 $x,y$ 满足 $posa[x]=posb[y]$，那它们就可以匹配，如果我们能计数每个集合对应的值的个数 $cnta,cntb$，若 $\exists \ ,S$ , $cnta[S]\neq cntb[S]$，则答案为 $0$ 。否则答案就是

$$\prod_S cnta[S]!$$

问题转化为如何更新某个值对应的位置集合，以及计数相同的集合，考虑集合哈希，用哈希表维护集合对应值的出现次数，每次加入一个位置是 $O(1)$ 的。

对于 $q$ 次询问，使用莫队即可做到 $O(n\sqrt q)$。

---

100 pts

考虑更为具体的刻画：用二分图表示 $A,B$ 中值的映射关系，在每一对匹配的 $x,y$ 间连边，这样每个位置会连出两个三元集合间的 $9$ 条边，一个区间的边相当于对每个值在不同位置的边求交后剩下的边。

Observation 1

区间合法的充要条件是区间内的值对应的二分图存在完美匹配。

Observation 2

每个连通块的边一定连满，形式化地，若存在匹配边 $a\leftrightarrow x,b\leftrightarrow x,b\leftrightarrow y$，则存在匹配边 $a\leftrightarrow y$。

上述性质由集合哈希的结论不难得到。

考虑如何计算答案，由于连通块大小最大为 $3$，维护大小为 $1,2,3$ 的连通块个数 $a,b,c$，答案即为

$$1^a\cdot 2^b\cdot 6^c\cdot (m-a-2b-3c)!$$

而由于结论二，我们只需维护每个点的度数即可求出 $a,b,c$，所以我们只需要维护每一条边对点的度数带来的影响。

• 上述性质结论只在区间存在合法解时成立，于是我们先对每个询问区间求出其是否存在合法解，方法见文末。

考虑每个位置对应的 $9$ 条边什么时候有贡献，我们有：

Observation 3

对于一条边（这里认为端点相同，但出现位置不同的边不是一条边），存在 $L,R$，满足对于所有询问区间 $[l,r]$ 满足 $L\leq l\leq pos\leq r\leq R$ 的询问区间，这条边都存在，其中 $pos$ 是这条边的出现位置。

$proof:$ 由于我们只考虑特定的一条边，所以 $L,R$ 显然是独立的，又因为每次扩展询问区间只可能让两端点都已经出现的边消失，故能使这条边出现的区间左右端点都有单调性，取最小的左端点和最大的右端点即为 $L,R$。

由于区间存在合法解时两边的点本质相同，下面所有操作都只考虑一边的点。

• 注意上述的 $R$ 是对每一条边单独考虑的，若两条边端点相同，但出现位置不同，可能使得有的位置同时存在这两条边，所以我们把 $R$ 与下一条端点相同的边的 $pos-1$ 取 $min$ 即可去重。

求解 $L,R$ 是平凡的，这里以求解 $L$ 为例，设当前边的两端点是 $a,b$，我们找到其上一次出现的位置 $pa,pb$，若 $pa\neq pb$，则 $L=\max(pa,pb)+1$，否则当前边的 $L$ 等于 $pa$ 位置那条边的 $L$，直接继承其值即可。

考虑扫描线右端点，我们对每个值维护一个数组 $deg$，$deg[i]$ 表示左端点为 $i$ 时当前值对应点的度数，在扫到 $pos$ 时对 $[L,pos]$ 区间 $+1$。扫到 $R$ 时区间 $-1$，注意到一个点最多有三条边，且这三条边对应区间的右端点都相同，故 $deg$ 数组最多只有三段不同的取值，于是我们直接维护三段对应的左端点和一个右端点的位置，即可得到值为 $1,2,3$ 的区间。

我们需要得到对于左端点的每个位置 $i$，$deg[i]=1/2/3$ 的数有多少，操作为区间加减，单点查询，树状数组维护即可。

---

• 判断合法：考虑对于固定的询问区间右端点 $r$，其对应的 $l$ 有单调性。
  • 集合哈希：双指针找到最左边的合法 $l$ 即可
  • 二分图：区间对应的点存在完美匹配等价于每个位置都存在大小为 $3$ 的完美匹配，求出每条边存在区间的左端点后，对每个位置对应的 $9$ 个左端点暴力判断其是否有完美匹配即可。

code ：

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define mod 998244353
#define st first
#define ed second
#define pb push_back
#define il inline
#define R(x) x.begin(),x.end()
il int read(){
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+(ch^48);
		ch=getchar();
	}
	return x;
}
int n,m,q,A[N][3],B[N][3];
int f[N][3][3],g[N][3][3],L[N];
pii pre[2][N];
int nxt[2][N];
vector<int> t;
il bool check(int p,int tim){
	for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int a=0;a<3;a++)for(int b=0;b<3;b++)
		if(i!=a&&j!=b&&f[p][i][j]<tim&&f[p][a][b]<tim&&f[p][3-i-a][3-j-b]<tim)return 1;
	return 0;
}
vector<pii> Q[N];
int tr[3][N];
il int lowbit(int x){
	return x&(-x);
}
il void upd(int p,int x,int k){
	for( ;x<=n;x+=lowbit(x))
		tr[p][x]+=k;
}
il int query(int p,int x){
	int ans=0;
	for( ;x>=1;x-=lowbit(x))
		ans+=tr[p][x];
	return ans;
}
int l[N][4];
vector<pii> del[N];
il void Add(int x){
	if(l[x][0]==INF)return ;
	for(int i=0;i<3;i++){
		if(l[x][i+1]==INF)return ;
		upd(i,l[x][i],1),upd(i,l[x][i+1],-1);
	}
}
il void Del(int x){
	if(l[x][0]==INF)return ;
	for(int i=0;i<3;i++){
		if(l[x][i+1]==INF)return ;
		upd(i,l[x][i],-1),upd(i,l[x][i+1],1);
	}
}
long long fac[N];
il long long qpow(long long x,int n){
	long long ans=1;
	while(n){
		if(n&1)ans=ans*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return ans;
}
long long ans[N];
signed main(){
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++)A[i][0]=read(),A[i][1]=read(),A[i][2]=read();
	for(int i=1;i<=n;i++)B[i][0]=read(),B[i][1]=read(),B[i][2]=read();
	for(int i=1;i<=m;i++)pre[0][i]=pre[1][i]={0,-1},nxt[0][i]=nxt[1][i]=n+1;
	for(int i=n;i>=1;i--){
		for(int j=0;j<3;j++)for(int k=0;k<3;k++)
			g[i][j][k]=min(nxt[0][A[i][j]],nxt[1][B[i][k]]);
		for(int j=0;j<3;j++)nxt[0][A[i][j]]=nxt[1][B[i][j]]=i;
	}
	for(int i=1;i<=n;i++){
		t.clear();
		for(int j=0;j<3;j++)for(int k=0;k<3;k++){
			if(pre[0][A[i][j]].st==pre[1][B[i][k]].st){
				int pos=pre[0][A[i][j]].st;
				if(pos==0)f[i][j][k]=0;
				else f[i][j][k]=f[pos][pre[0][A[i][j]].ed][pre[1][B[i][k]].ed];
			}
			else f[i][j][k]=max(pre[0][A[i][j]].st,pre[1][B[i][k]].st);
			t.pb(f[i][j][k]);
		} 
		for(int j=0;j<3;j++) pre[0][A[i][j]]=pre[1][B[i][j]]={i,j};
		sort(R(t),greater<int>());
		for(unsigned int j=0;j<t.size();j++){
			if(j!=t.size()-1&&t[j]==t[j+1])continue;
			if(!check(i,t[j])){
				L[i]=max(L[i],t[j]+1);
				break;
			}
		}
	}
	for(int i=1;i<=n;i++)
		L[i]=max(L[i],L[i-1]);
	for(int i=1;i<=q;i++){
		int l=read(),r=read();
		if(L[r]<=l)Q[r].pb({l,i});
	}
	for(int i=1;i<=m;i++)l[i][0]=l[i][1]=l[i][2]=l[i][3]=INF;
	fac[0]=1;
	for(int i=1;i<=m;i++)fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=1;i<=n;i++){
		for(auto x:del[i]){
			Del(x.st);
			for(int j=0;j<3;j++){
				if(l[x.st][j]==x.ed){
					l[x.st][j]=INF;
					break;
				}
			}
			sort(l[x.st],l[x.st]+4);
			Add(x.st);
		}
		for(int j=0;j<3;j++){
			int a=A[i][j];
			Del(a);
			l[a][3]=i+1;
			for(int k=0;k<3;k++){
				l[a][k]=f[i][j][k]+1;
				del[g[i][j][k]].pb({a,l[a][k]});
			}
			sort(l[a],l[a]+4);
			Add(a);
		}
		for(auto x:Q[i]){
			int a=query(0,x.st),b=query(1,x.st),c=query(2,x.st);
			ans[x.ed]=1ll*qpow(6,c/3)*qpow(2,b/2)%mod*fac[m-a-b-c]%mod;
		}
	}
	for(int i=1;i<=q;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}