Rearrange Query の解説

zobrist hashを用いる。 各値について、ランダムな値を振り分ける。 このとき、衝突しなければ、各集合の和が異なることになるので累積和を使って前計算することで単なる数値の引き算で集合の一致を判定することができる。

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
        b: [usize; n],
        lrlr: [(Usize1, usize, Usize1, usize); q]
    }
    let ma = {
        let &a = a.iter().max().unwrap();
        let &b = b.iter().max().unwrap();
        max(a, b)
    };
    let hash = ZobristHash::new(ma + 10);
    let a = a.iter().map(|&e| hash.hash(e)).collect_vec();
    let b = b.iter().map(|&e| hash.hash(e)).collect_vec();
    let mut acca = vec![0];
    for &num in a.iter() {
        let &la = acca.iter().last().unwrap();
        let next = hash.add(la, num);
        acca.push(next);
    }
    let mut accb = vec![0];
    for &num in b.iter() {
        let &la = accb.iter().last().unwrap();
        let next = hash.add(la, num);
        accb.push(next);
    }
    for &(l1, r1, l2, r2 ) in lrlr.iter() {
        let s1 = hash.sub(acca[r1], acca[l1]);
        let s2 = hash.sub(accb[r2], accb[l2]);
        let ans = if s1 == s2 {"Yes"} else {"No"};
        println!("{}", ans);
    }
}