test/Hash/zobrist_hash/yukicoder-12925.cpp

View this file on GitHub
Last update: 2025-12-01 19:44:23+09:00
Problem: https://yukicoder.me/problems/12925

Depends on

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/12925

#include "Hash/zobrist_parity_hash.hpp"
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N, Q;
    cin >> N >> Q;

    vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    ZobristParityHash zh(A);

    for (int q = 0; q < Q; q++)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        l1--, l2--;

        if (zh.get_range_hash(l1, r1) == zh.get_range_hash(l2, r2))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }

    return 0;
}

#line 1 "test/Hash/zobrist_hash/yukicoder-12925.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/12925

#line 1 "Hash/zobrist_hash_base.hpp"
#include <bits/stdc++.h>
using namespace std;

class ZobristHashBase
{
private:
    static unsigned long long splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    static unsigned long long generate_random_value(unsigned long long x)
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }

protected:
    static unsigned long long hash(long long x)
    {
        static unordered_map<long long, unsigned long long> cache;
        if (cache.contains(x))
        {
            return cache[x];
        }

        cache[x] = generate_random_value(x);
        return cache[x];
    };

    virtual void build(const vector<long long> &v) = 0;
    ZobristHashBase() {};

public:
    vector<unsigned long long> hash_vector;
    virtual unsigned long long get_range_hash(int l, int r) const = 0;
    virtual ~ZobristHashBase() = default;
};
#line 2 "Hash/zobrist_parity_hash.hpp"

#line 4 "Hash/zobrist_parity_hash.hpp"
using namespace std;

class ZobristParityHash : private ZobristHashBase
{
private:
    void build(const vector<long long> &v) override
    {
        hash_vector = vector<unsigned long long>(v.size() + 1, 0);
        for (int i = 0; i < v.size(); i++)
        {
            hash_vector[i + 1] = hash_vector[i] ^ ZobristHashBase::hash(v[i]);
        }
    }

public:
    unsigned long long get_range_hash(int l, int r) const override
    {
        assert(0 <= l && l < r && r < hash_vector.size());
        return hash_vector[r] ^ hash_vector[l];
    }

    ZobristParityHash(const vector<long long> &v)
    {
        build(v);
    };
};
#line 5 "test/Hash/zobrist_hash/yukicoder-12925.cpp"

using namespace std;

int main()
{
    int N, Q;
    cin >> N >> Q;

    vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    ZobristParityHash zh(A);

    for (int q = 0; q < Q; q++)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        l1--, l2--;

        if (zh.get_range_hash(l1, r1) == zh.get_range_hash(l2, r2))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	01_small_1.txt	AC	6 ms	3 MB
g++	01_small_10.txt	AC	5 ms	3 MB
g++	01_small_2.txt	AC	5 ms	3 MB
g++	01_small_3.txt	AC	5 ms	3 MB
g++	01_small_4.txt	AC	5 ms	3 MB
g++	01_small_5.txt	AC	5 ms	3 MB
g++	01_small_6.txt	AC	5 ms	3 MB
g++	01_small_7.txt	AC	5 ms	3 MB
g++	01_small_8.txt	AC	5 ms	3 MB
g++	01_small_9.txt	AC	5 ms	3 MB
g++	02_big_1.txt	AC	472 ms	16 MB
g++	02_big_10.txt	AC	440 ms	16 MB
g++	02_big_2.txt	AC	526 ms	16 MB
g++	02_big_3.txt	AC	432 ms	16 MB
g++	02_big_4.txt	AC	423 ms	16 MB
g++	02_big_5.txt	AC	410 ms	16 MB
g++	02_big_6.txt	AC	422 ms	16 MB
g++	02_big_7.txt	AC	557 ms	16 MB
g++	02_big_8.txt	AC	463 ms	16 MB
g++	02_big_9.txt	AC	485 ms	16 MB