2025.4.15
1.NOI2024 集合
1.基本集合就是大小为3，元素在1-m的集合
2.集合序列就是基本集合构成的序列
3.f_p(s)={p[x]|x属于S}
4.A和B等价：存在一个1-m的排列p，f_p(A[i])=B[i] (1<=i<=k)
5.给定集合序列A,B
询问集合序列[A[L],…,A[r]]与[B[l],…,B[R]]是否等价

如果翻译一下题目就是
检测是否能自己构造一个排列P，然后对A[i]变换后，变成B[i]

排列 函数对应关系 如果能哈希来做就好了

思考能不能哈希

先思考怎么打暴力
最暴力当然是暴力枚举P，然后看看符不符合

这种做法，暴力枚举P看起来不好优化(最naive当然就是next_permutation)
看看检测符不符合的时候能不能优化时间
短时间没想出来

观察一下：说些没啥用的性质
1.
A是1 2 3
B是2 3 4
那P[1]=2,p[2]=3,p[3]=4
A是1 2 4
B是1 2 3
那P[1]=1,p[2]=2,p[4]=3

wait,突然发现理解错题意了
原来不需要对应，只需要存在在这个集合就好
就是说
A是1 2 4
B是1 2 3
那P[1]=2,p[2]=3,p[4]=1
也行，因为最后生成的数字组合就是1 2 3

这就难办了，怎么验证呢

偷开题解发现是哈希，但是想不出应该如何哈希

理论上来说，三个元素，而不是变量个元素，应该是性质入手点，但是还是没想到

打开题解，发现关键观察是
两个子序列等价的条件是
每个元素x在A中出现位置集合
与
每个元素y在B中出现位置集合
相同

这时候我们思考一下，这个性质是怎么思考和观察出来的，我们下次遇到应该如何发现

1.多感受样例
2.多思考这个变换实际代表了什么
3.实际上这个f_p操作就是位置的哈希，或者是转换

知道这个性质之后，我们可以对每个位置集合给一个哈希值，然后比较

我们会发现，对于固定的l，随着r增加，等价条件会越来越严格。因此可以预处理每个l最大的r(就是有单调性，于是可以预处理，询问就可以直接出答案)

#include <bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5,M=6e5+5;  // 定义常量N和M，分别表示数组的最大长度和元素的最大值
using llu=long long unsigned;    // 定义llu为unsigned long long类型

int n,m,q,tor[N];                // n:序列长度, m:元素范围, q:询问次数, tor[i]:记录每个l对应的最大r
int a[N][3],b[N][3];            // 存储两个集合序列A和B的每个集合的3个元素

// 随机数生成器，用于生成哈希种子
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());

llu mp[N];      // 存储每个位置的随机哈希值
llu ap[M],bp[M];// 存储A和B中每个元素的哈希累加值
llu s1,s2;      // 存储A和B当前窗口的哈希总和
llu msk;        // 随机掩码，用于哈希混淆

// 哈希混淆函数
llu shf(llu x){
    if(!x) return x;
    x^=msk,x^=x<<7,x^=x>>11,x^=x<<13;  // 通过位运算进行哈希混淆
    return x;
}

// 添加或移除第i个集合的贡献
void add(int i,int d){
    // 处理A序列
    for(int j:a[i]){
        s1-=shf(ap[j]);         // 移除旧的哈希值
        if(d>0) ap[j]+=mp[i];   // 根据d的正负决定是添加还是移除
        else ap[j]-=mp[i];
        s1+=shf(ap[j]);         // 添加新的哈希值
    }
    // 处理B序列
    for(int j:b[i]){
        s2-=shf(bp[j]);
        if(d>0) bp[j]+=mp[i];
        else bp[j]-=mp[i];
        s2+=shf(bp[j]);
    }
}

int main(){
    // 关闭同步，加速输入输出
    cin.tie(0)->sync_with_stdio(0);

    // 输入数据
    cin>>n>>m>>q;
    for(int i{1};i<=n;++i){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    }
    for(int i{1};i<=n;++i){
        cin>>b[i][0]>>b[i][1]>>b[i][2];
    }

    // 初始化tor数组，初始值为n
    for(int i{1};i<=n;++i) tor[i]=n;

    // 进行10次随机哈希检查，提高正确率
    int tt=10;
    while(tt--){
        msk=rnd();  // 生成随机掩码
        for(int i{1};i<=n;++i) mp[i]=rnd();  // 为每个位置生成随机哈希值

        // 初始化双指针
        add(1,1);  // 添加第一个集合的贡献
        for(int i{1},j{1};i<=n;add(i,-1),++i){  // 移动左指针i
            while(j<=n&&s1==s2){  // 当哈希和相等时，尝试扩展右指针j
                ++j;
                if(j<=n) add(j,1);
            }
            tor[i]=min(tor[i],j-1);  // 更新tor[i]
        }
    }

    // 处理询问
    while(q--){
        int l,r; cin>>l>>r;
        if(r<=tor[l]) cout<<"Yes\n";  // 如果r在tor[l]范围内，输出Yes
        else cout<<"No\n";
    }
    return 0;
}