Submission #51889578

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef pair<int, int> Pair;
typedef tuple<int, int, int> tpl;

#define ALL(a) (a).begin(), (a).end()
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(c) reverse((c).begin(), (c).end())
#define LB(a, x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a, x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define RREP(i, n) RFOR(i, n, 0)

#define en "\n"

constexpr double EPS = 1e-9;
constexpr double PI = 3.1415926535897932;
constexpr int INF = 2147483647;
constexpr long long LINF = 1LL << 60;
constexpr long long MOD = 998244353; // 1000000007;

template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
struct Problem {
    VI cnt;
    vector<vector<Pair>> fact;
    int sum;

    Problem(vector<vector<Pair>> fact) : fact(fact) {
        cnt.resize(1000100, 0);
        sum = 0;
    }

    void add_id(int i) {
        // process for adding index i
        for (auto &[p, n] : fact[i]) {
            sum -= cnt[p] % 3;
            cnt[p] += n;
            sum += cnt[p] % 3;
        }
    }
    void erase_id(int i) {
        // process for erasing index i
        for (auto &[p, n] : fact[i]) {
            sum -= cnt[p] % 3;
            cnt[p] -= n;
            sum += cnt[p] % 3;
        }
    }
    T get_answer() {
        // return current answer
        return sum == 0;
    }
};

struct Segment {
    int L, R, query_id, block_id;
    Segment(int L, int R, int query_id, int block_id) : L(L), R(R), query_id(query_id), block_id(block_id) {}

    std::tuple<int, int, int> get_key() const {
        if (block_id & 1) {
            return std::make_tuple(block_id, -R, L);
        }
        return std::make_tuple(block_id, R, L);
    }
};

bool operator<(const Segment &lhs, const Segment &rhs) {
    return lhs.get_key() < rhs.get_key();
}

template <class T>
struct Mo {
    int N, Q, sqrt_Q;
    std::vector<int> L, R;

    Mo(int N, int Q, std::vector<int> L, std::vector<int> R) : N(N), Q(Q), L(L), R(R) {
        this->sqrt_Q = calc_sqrt(Q);
    }

    std::vector<Segment> get_sorted_segments() {
        std::vector<Segment> segments;
        for (int i = 0; i < Q; i++) {
            segments.push_back(Segment(L[i], R[i], i, L[i] / sqrt_Q));
        }
        std::sort(segments.begin(), segments.end());
        return segments;
    }

    std::vector<T> solve(Problem<T> p) {
        int l = 0, r = 0;
        std::vector<Segment> segments = get_sorted_segments();
        std::vector<T> answers(Q);

        for (Segment &segment : segments) {
            int l_next = segment.L, r_next = segment.R;

            if (r < r_next) {
                for (int i = r; i < r_next; i++) {
                    p.add_id(i);
                }

                if (l < l_next) {
                    for (int i = l; i < l_next; i++) {
                        p.erase_id(i);
                    }
                } else {
                    for (int i = l - 1; i >= l_next; i--) {
                        p.add_id(i);
                    }
                }
            } else {
                if (l < l_next) {
                    for (int i = l; i < l_next; i++) {
                        p.erase_id(i);
                    }
                } else {
                    for (int i = l - 1; i >= l_next; i--) {
                        p.add_id(i);
                    }
                }

                for (int i = r - 1; i >= r_next; i--) {
                    p.erase_id(i);
                }
            }

            answers[segment.query_id] = p.get_answer();
            l = l_next;
            r = r_next;
        }

        return answers;
    }

  private:
    int calc_sqrt(int x) {
        int ng = 0, ok = sqrt(x) + 2;
        while (ok - ng > 1) {
            int m = (ok + ng) / 2;
            if (m * m < x)
                ng = m;
            else
                ok = m;
        }
        return ok;
    }
};

struct SieveEratosthenes {
    vector<int> min_fact;

    SieveEratosthenes(int N) {
        _build(N);
    }

    void _build(int N) {
        min_fact.resize(N + 1);
        for (int i = 0; i <= N; i++)
            min_fact[i] = i;

        min_fact[0] = min_fact[1] = -1;

        for (int i = 2; i * i <= N; i++) {
            for (int j = i * i; j <= N; j += i) {
                if (i < min_fact[j])
                    min_fact[j] = i;
            }
        }
    }

    bool is_prime(int x) {
        return min_fact[x] == x;
    }

    vector<pair<int, int>> factorize(int x) {
        vector<pair<int, int>> ret;
        while (x > 1) {
            if (ret.empty() || ret.back().first != min_fact[x])
                ret.emplace_back(min_fact[x], 1);
            else
                ret.back().second++;

            x /= min_fact[x];
        }

        return ret;
    }
};

void Main() {
    int N, Q;
    cin >> N >> Q;
    VI A(N);
    REP(i, N)
    cin >> A[i];
    SieveEratosthenes sieve(1000100);
    vector<vector<Pair>> fact(N);
    REP(i, N) {
        fact[i] = sieve.factorize(A[i]);
    }

    VI L(Q), R(Q);
    REP(i, Q)
    cin >> L[i] >> R[i],
        L[i]--;

    Problem<int> p(fact);
    Mo<int> mo(N, Q, L, R);

    vector<int> ans = mo.solve(p);
    REP(i, Q)
    cout << (ans[i] ? "Yes" : "No") << en;
    return;
}

int main(void) {
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(15);
    int t = 1; // cin>>t;
    while (t--)
        Main();
    return 0;
}

Submission Info

Judge Result