[Hackerearth] Prime Query

 

Problem Link    : Prime Query
Category        : Math
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n;
        cin >> n;
        vector<int> arr(n + 1);
        vector<vector<int>> cumsum(n + 1, vector<int>(2));
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
            for (int j = 0; j < 2; j++) {
                cumsum[i][j] = cumsum[i - 1][j] + (arr[i] == j);
            }
        }
        int q;
        cin >> q;
        while (q--) {
            int l, r;
            cin >> l >> r;
            int zeros = cumsum[r][0] - cumsum[l - 1][0];
            int ones = cumsum[r][1] - cumsum[l - 1][1];
            int len = r - l + 1;
            int ans = len * (len - 1) / 2 - (zeros * ones);
            ans -= zeros * (zeros - 1) / 2;
            cout << ans << endl;
        }
    }