P10785 [NOI2024] 集合

· · 题解

如果一个区间是合法的，那么它的所有子区间都合法；由此可以双指针预处理出 mx_l 表示当 r\le mx_l 时区间 [l,r] 是合法的。

如果存在一组映射，其中 p_x=y，那么有：

\{p|x\in A_p\}=\{p|y\in B_p\}

由此可以定义两个集合：

S_A=\{\{p|1\in A_p\},\{p|2\in A_p\},\dots,\{p|m\in A_p\}\} S_B=\{\{p|1\in B_p\},\{p|2\in B_p\},\dots,\{p|m\in B_p\}\}

当 S_A=S_B 时，就存在一组映射，即区间合法。

结合上述双指针，现在每次需要修改 S_A,S_B 子集合中的一个位置，判断 S_A,S_B 是否相同，考虑使用哈希：先将下标映射成随机数，然后对子集合使用异或和，对外层集合使用加和，即：

\operatorname{HASH}(S_A)=\sum_{x=1}^m\bigoplus_{x\in A_p}f(p) \operatorname{HASH}(S_B)=\sum_{x=1}^m\bigoplus_{x\in B_p}f(p)

（具体实现时可以用 unsigned long long 自然溢出。）

当 \operatorname{HASH}(S_A)=\operatorname{HASH}(S_B) 时，即认为当前区间合法。

以下是去除了头文件的完整代码：

const int N=2e5+10,M=6e5+10;
int n,m,q,a[N][3],b[N][3],mx[N]; unsigned ll hsh[N],sa[M],sb[M],A,B; mt19937_64 rng((ll)(new char));

inline void chg(int x){
    for(int p=0;p<3;++p){
        A-=sa[a[x][p]],sa[a[x][p]]^=hsh[x],A+=sa[a[x][p]];
        B-=sb[b[x][p]],sb[b[x][p]]^=hsh[x],B+=sb[b[x][p]];
    }
}

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<=n;++i) hsh[i]=rng();
    for(int l=1,r=0;l<=n;chg(l++)){
        while(r<=n&&A==B) chg(++r);  mx[l]=r;
    }
    for(int l,r;q;--q) l=read(),r=read(),puts((r<mx[l])?"Yes":"No");
    return 0;
}