Prefix equality [DP | hash]

E - Prefix Equality

The question ： Give two sequences of integers a,b, Next is q Time to ask , Ask and give two integers x,y, ask a Before x Digit numbers and b Before y Whether the types of digits are exactly the same .

DP Thought ！

• We only care about a front x Information stored in digits and b front y Bit stored information
• What does information store ？ For this question , The numbers may be the same , We only care about where the numbers first appear , Store in prea Inside
• ansa For a Before x A digital ,b The maximum value of the coordinate where the corresponding number appears , If a Before x In the numbers b There is no certain number in , Set to inf.

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
int a[200010], b[200010];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin >> n;
    std::map<int, int> prea,preb;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        if(!prea.count(a[i]))prea[a[i]] = i;
    }
    for (int i = 1; i <= n; i ++ ) {
        cin >> b[i];
        if(!preb.count(b[i]))preb[b[i]] = i;
    }
    std::vector<int> ansa(n + 1, 0), ansb(n + 1, 0);
    for (int i = 1; i <= n; i ++ ) {
        ansa[i] = max(ansa[i - 1], preb.count(a[i]) ? preb[a[i]] : inf);
        ansb[i] = max(ansb[i - 1], prea.count(b[i]) ? prea[b[i]] : inf);   
    }
 
    int t;
    cin >> t;
    while(t -- ) {
        int x, y;
        cin >> x >> y;
        cout << ((ansb[y] <= x && ansa[x] <= y) ? "Yes" : "No") << '\n';
    }   
    return 0;
}

Hash

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll a[200010], b[200010];
set<ll> se;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    cin >> n;
    ll s = 0;
    for (int i = 1; i <= n; i ++ ) {
        ll x;
        cin >> x;
        if(se.find(x) == se.end()) {
            s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
        }
        a[i] = s;
        se.insert(x);
    }
    se.clear();
    s = 0;
    for (int i = 1; i <= n; i ++ ) {
        ll x;
        cin >> x;
        if(se.find(x) == se.end()) {
            s = (s + x * (x + 137) % mod * (x + 997) % mod) % mod;
        }
        b[i] = s;
        se.insert(x);
    }
    int t;
    cin >> t;
    while(t -- ) {
        int x, y;
        cin >> x >> y;
        if(a[x] == b[y]) {
            cout << "Yes\n";
        }
        else cout << "No\n";
    }   
    return 0;
}