Submission #48871873

---

Source Code Expand

#pragma GCC target("avx2,avx512f,avx512vl,avx512bw,avx512dq,avx512cd,avx512vbmi,avx512vbmi2,avx512vpopcntdq,avx512bitalg,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("Ofast")
//#undef LOCAL


#include <bitset>
#include <iostream>
#include <vector>

using namespace std;

const int SZ = 2000;
using B = bitset<SZ>;

B bs[200000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        c[i]--;
    }
    vector<pair<int, int>> ques(q);
    for (int i = 0; i < q; i++) {
        cin >> ques[i].first >> ques[i].second;
        ques[i].first--;
        ques[i].second--;
    }

    vector<int> ans(q);
    for (int ph = 0; ph < 100; ph++) {
        int st = SZ * ph;
        for (int i = 0; i < n; i++) {
            bs[i].reset();
            if (0 <= c[i] - st && c[i] - st < SZ) {
                bs[i].set(c[i] - st);
            }
        }
        for (int i = 0; i < q; i++) {
            int a = ques[i].first, b = ques[i].second;
            bs[b] |= bs[a];
            bs[a].reset();

            ans[i] += int(bs[b].count());
        }
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

Submission Info

Judge Result