把以前想的唐氏东西记录一下。

题目

当时什么 hash 状物都不会，但考虑一下哈希的本质，实际上是一种映射关系，在这一道题中，我们可以省掉哈希的进制，因为匹配的结果与位置无关，接下来就可以乱搞了。

是真的乱搞(意思是随便想一个与之关联的函数)，但是这个东西现在发现和 sum hash 很相似，实际上sum hash 只是赋了一个随机值而已。

code很上古

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=3e5+5,P=10260913;
ull suma[N],sumb[N];
ull qsm(int a,int b){
    ull ans=1;
    while(b){
        if(b&1)  ans=ans*a*1ull;
        a*=2,b>>=1;
    }
    return ans;
}
map<int,int>A,B;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        if(A[k]==0){
            A[k]=1;
            suma[i]=suma[i-1]+qsm(k,k)*k+(P-k)*P;
        }
        else{
            suma[i]=suma[i-1];
        }
    }
    for(int i=1;i<=n;i++){
        int k;cin>>k;
        if(B[k]==0){
            B[k]=1;
            sumb[i]=sumb[i-1]+qsm(k,k)*k+(P-k)*P;
        }
        else{
            sumb[i]=sumb[i-1];
        }
    }
    int q;cin>>q;
    while(q--){
        int a,b;cin>>a>>b;
        if(suma[a]==sumb[b]){
            puts("Yes");
        }else{
            puts("No");
        }
    }
}