T1

#include<bits/stdc++.h>
using namespace std;

// 可以二分长度 len

// 已知长度为 len 

// 求出是否存在一种子串重复出现了 k 次

// 想办法把长度为 len 的子串做次数上的统计
// 高维状态 {1, 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3}
//                             3 * p ^ 3 +  1 * p^2 + 2 * p + 3 * 1
// 哈希压缩成一维的状态

const int P = 13333331; //-> 如果不是质数，哈希冲突可能会比较大
#define ull unsigned long long
vector<ull> pw;//进制的位权
vector<ull> h;//哈希值
vector<ull> a;
int main(){
    int n , k;
    cin >> n >> k;
    a.resize(n + 1);
    h.resize(n + 1);
    pw.resize(n + 1);
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
    }
    pw[0] = 1;
    for(int i = 1 ; i <= n ; i ++){
        pw[i] = pw[i - 1] * P;
    }
    // 1 
    // 12
    // 12 = 1 * 10 + 2
    // 123 = 12 * 10 + 3
    // 1231 = 123 * 10 + 1
    for(int i = 1 ; i <= n ; i ++){
        //a[1]是最高位
        //a[2]是第二位
        //a[n]是最低位
        //a[1]a[2]a[3]...a[i] = a[1]a[2]a[3]...a[i-1] * P + a[i]
        h[i] = h[i - 1] * P + a[i];
    }
    //h[i] : a[1] ~ a[i] 的 Hash 值
    // 求a[l] ~ a[r] 的 Hash 值
    // 现有Hash值  ： 123451 [23451] 234512345
    // 12345123451 ：h[r]
    // - 12345100000: h[l-1] * p^(r-l+1)
    // = 23451 
    // a[l] ~ a[r] = h[r] - h[l-1] * pw[r-l+1]
    auto get_hash =[&](int l , int r){
        return h[r] - h[l - 1] * pw[r - l + 1];
    };
    auto check =[&](int len){
        //把每个长度为len的子串压缩成一个数字
        map<ull,int>mp;
        for(int i = len ; i <= n ; i ++){
            //把每个长度为len的子串的哈希值存在map里面
            ull hash = get_hash(i - len + 1 , i);
            mp[hash]++;
            if(mp[hash] >= k){
                return true;
            }
        }
        return false;
    };
    int l = 1 , r = n;
    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(check(mid)){
            l = mid;
        }
        else{
            r = mid - 1;
        }
    }
    cout << l << endl;
} 

T2

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 2e5 + 10;
//随机数生成器
mt19937_64 rnd(114514);
//集合不关心顺序，只关心具体的元素
//前缀哈希值
ull prea[N];
ull preb[N];
map<int,ull>mp;
int main(){
    int n;
    cin >> n;
    //只需要处理一个数第一次出现的时候就可以了
    //集合：需要去重
    //只需要在第一次出现的时候加入到前缀和里面
    map<int,int>cnt;
    for(int i = 1 ; i <= n ; i ++){
        int x;
        cin >> x;
        cnt[x]++;
        prea[i] = prea[i - 1];
        if(cnt[x] == 1){
            mp[x] = rnd();
            prea[i] += mp[x];
        }
    }
    cnt.clear();
    for(int i = 1 ; i <= n ; i ++){
        int x;
        cin >> x;
        cnt[x]++;
        preb[i] = preb[i - 1];
        if(cnt[x] == 1){
            if(mp.count(x)){
                preb[i] += mp[x];
            }
            else{
                mp[x] = rnd();
                preb[i] += mp[x];
            }
        }
    }
    int q;
    cin >> q;
    while(q--){
        int x , y;
        cin >> x >> y;
        if(prea[x] == preb[y]){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
} 

T3

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N = 2e5 + 10;
//随机数生成器
mt19937_64 rnd(114514);
//集合不关心顺序，只关心具体的元素
//前缀哈希值
ull prea[N];
ull preb[N];
map<int,ull>mp;
int main(){
    int n , q;
    cin >> n >> q;
    //只需要处理一个数第一次出现的时候就可以了
    //集合：需要去重
    //只需要在第一次出现的时候加入到前缀和里面
    for(int i = 1 ; i <= n ; i ++){
        int x;
        cin >> x;
        prea[i] = prea[i - 1];
        if(mp.count(x)){
            prea[i] += mp[x];
        }
        else{
            mp[x] = rnd();
            prea[i] += mp[x];
        }
    }
    for(int i = 1 ; i <= n ; i ++){
        int x;
        cin >> x;
        preb[i] = preb[i - 1];
        if(mp.count(x)){
            preb[i] += mp[x];
        }
        else{
            mp[x] = rnd();
            preb[i] += mp[x];
        }
    }
    while(q--){
        int l1 , r1 , l2 , r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if(prea[r1] - prea[l1 - 1] == preb[r2] - preb[l2 - 1]){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
} 

T4

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

#define ull unsigned long long

vector<int> vis(N + 1 , 0);
vector<int> primes;

mt19937_64 rnd(time(0));

int val[3] = {-5 , 2 , 3};

void sieve(){
    for(int i = 2 ; i < N ; i++){
        if(!vis[i]){
            primes.push_back(i);

            for(long long j = 1LL * i * i ; j < N ; j += i){
                vis[j] = 1;
            }
        }
    }
}

ull pre[N];
ull mp[N];

int cnt[N];
int a[N];

int main(){
    sieve();

    int n , q;
    cin >> n >> q;

    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }

    // 每一个质数随机一个 Hash
    for(auto p : primes){
        mp[p] = rnd();
    }

    for(int i = 1 ; i <= n ; i++){
        int x = a[i];

        pre[i] = pre[i - 1];

        for(auto p : primes){

            // 剩下的 x 如果不是 1，那么一定是质数
            if(1LL * p * p > x){
                break;
            }

            while(x % p == 0){
                cnt[p]++;

                // 1 -> +2
                // 2 -> +3
                // 0 -> -5
                pre[i] += val[cnt[p] % 3] * mp[p];

                x /= p;
            }
        }

        // 剩余的大质因子
        if(x > 1){
            cnt[x]++;

            pre[i] += val[cnt[x] % 3] * mp[x];
        }
    }

    while(q--){
        int l , r;
        cin >> l >> r;

        if(pre[r] == pre[l - 1]){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }

    return 0;
}

T5

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
#define ull unsigned long long
vector<int> vis(N + 1 , 0);
mt19937_64 rnd(time(0));
// 恰好为3
// 1.3的倍数 -> 哈希
// 2.不大于3  -> 滑动窗口(双指针)保证窗口内的所有数字出现次数不超过3
//只考虑3的倍数
//求 pre[r] == pre[l] 的个数
//考虑恰好为3
//1.必须是3的倍数
//2.用滑动窗口来确保 [l ~ r] 的每个数字都不超过 3 
int val[3] = {-3 , 1 , 2};
ull pre[N];
ull mp[N];
int cnt[N];
int a[N];
int main(){
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    //先把 1 ~ n 哈希值设置
    for(int i = 1 ; i <= n ; i ++){
        mp[i] = rnd();
    }
    map<ull , int> cnt_pre;//cnt_pre[x] 表示滑窗里面 pre[l] == x 的个数
    map<int , int> num;
    int l = 0;
    cnt_pre[0] = 1;
    long long ans = 0;
    for(int r = 1 ; r <= n ; r++){
        //a[r] 是原本的值
        ull hash = mp[a[r]];
        cnt[a[r]]++;//出现次数
        pre[r] = pre[r - 1] + val[cnt[a[r]] % 3] * hash;
        num[a[r]]++;//滑窗里面的次数
        //滑窗保证 [l ~ r] 的所有数字都不超过 3
        while(num[a[r]] > 3){
            //去掉原本的pre[l]
            cnt_pre[pre[l]]--;
            l++;
            num[a[l]]--;
        }
        //好数组 pre[r] == pre[l]
        //统计好数组的个数 -> 统计 pre[l] == pre[r] 的次数
        ans += cnt_pre[pre[r]];
        cnt_pre[pre[r]]++;
    }
    //区间是好数组 ： pre[r] == pre[l]
    //pre[r] - pre[l] == 0 , 需要记录出现次数 
    cout << ans << endl;
    return 0;
}