bs-io-practice-01.cpp

int solve(vector<int>& A, vector<int>& T) {
    // total - number of sublists that contain target
    // [1, 2, 3, 4, 5], T = [2, 4]
    const int N = A.size();
    const int MOD = 1e9 + 7;
    const int INF = 1e9;
    if (T.empty()) return 0;
    sort(T.begin(), T.end());
    long long tot = 1ll * N * (N + 1) / 2;
    long long contain = 0;
    unordered_map<int,int> pos;
    multiset<int> vals;
    for (int x: T) {
        pos[x] = -INF;
        vals.insert(-INF);
    }
    for (int i = 0; i < N; i++) {
        if (binary_search(T.begin(), T.end(), A[i])) {
            int old = pos[A[i]];
            vals.erase(vals.find(old));
            pos[A[i]] = i;
            vals.insert(i);
        }
        pos[A[i]] = i;
        int j = *vals.begin();
        if (j == -INF) continue;
        contain += j + 1;
        if (contain >= MOD) contain -= MOD;
    }
    int ans = (tot - 1ll * contain + MOD) % MOD;
    return ans;
}