問題概要

2 つのサイズ $N$ の整数列 $a_{0}, a_{1}, \dots, a_{N-1}$ と $b_{0}, b_{1}, \dots, b_{N-1}$ が与えられます。

これらの数列に対して $Q$ 回のクエリが与えられます。各クエリでは $N$ 以下の整数 $x, y$ が与えられますので、

数列 $a$ の先頭から $x$ 個の要素： $a_{0}, a_{1}, \dots, a_{x-1}$
数列 $b$ の先頭から $y$ 個の要素： $b_{0}, b_{1}, \dots, b_{y-1}$

が集合として一致するかどうかを判定してください。

制約

$1 \le N, Q \le 2 \times 10^{5}$

解法 1：ハッシュで殴る

この問題の難しさは

各 $i = 0, 1, \dots, N$ に対して、各数列の先頭から $i$ 個とってできる集合を求めたいが、それらすべて保存するのはメモリが足りない
各クエリに対して、集合が一致するかどうかを判定するには $O(N)$ の時間を要する (std::set の場合は $O(N \log N)$ )

というところにあります。しかしこれらの問題を一度にまとめて解決してしまう方法があります。それは Zobrist Hash などのハッシュを使う方法です。

各 $x = 0, 1, \dots, N$ に対して、 $a_{0}, a_{1}, \dots, a_{x-1}$ からなる集合を 1 つの整数値として表現してしまうのです。

そのようなことが可能なハッシュであればなんでもよいのですが、集合をハッシュ値で表すには Zobrist Hash が便利です。その方法はいたって簡単です！

集合の各要素に対して乱数を割り当てる
割り当てた乱数の XOR をとる

乱数を割り当てる部分は、いい感じの関数があります。Codeforces ブログで提供されているので、これをパクらせてもらいましょう！！！

実行してみないと値が分からない chrono::steady_clock::now().time_since_epoch().count() を活用しているため、とても強いです。

codeforces.com

総合して、計算量は $O(N \log N + Q)$ です。

Zobrist Hash についての remark

Zobrist Hash は XOR をとるものであるため、要素の「挿入」と「削除」がともに高速にできます
Zobrist Hash は「要素の種類」のみに対応しているため、「要素の個数」まで知りたい場合は、XOR をとる代わりに「普通の和」をとります (参考：chokudai さんのツイート)

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

// 整数値 x にハッシュ値を割り当てる関数
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator() (uint64_t x) const {
        static const uint64_t FIXED_RANDOM =    
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
} rng;

int main() {
    // Zobrist Hash
    // hashA[i] := 数列 a の先頭から i 個分の集合を表すハッシュ値
    int N;
    cin >> N;

    // N 個の入力を受け取って、Zobrist Hash を返す関数
    auto hashing = [&]() -> vector<uint64_t> {
        vector<uint64_t> hash(N + 1, 0);
        set<long long> S;  // すでにあるかを確認する

        for (int i = 0; i < N; ++i) {
            long long x;
            cin >> x;

            // すでに含まれている場合は何もしない
            if (S.count(x)) {
                hash[i + 1] = hash[i];
                continue;
            }
            S.insert(x);
            hash[i + 1] = hash[i] ^ rng(x);
        }
        return hash;
    };

    const auto& hashA = hashing();
    const auto& hashB = hashing();

    // クエリ処理
    int Q;
    cin >> Q;
    while (Q--) {
        int x, y;
        cin >> x >> y;
        if (hashA[x] == hashB[y]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}