The Root of Evil#11697

The Root of Evil (Editorial)

Group 1: $n \leq 500$ n \leq 500, $q \leq 500$ q \leq 500, $a_{i} \leq 500$ a_i \leq 500, in each query $x \leq 500$ x \leq 500

In this group, the straightforward solution would pass, so let's just maintain a multiset of elements and for each query of 3 type just iterate through each pair of elements and check if $⌊ \frac{p}{q} ⌋ = x$ \lfloor\frac{p}{q}\rfloor = x.

int n;
cin >> n;
multiset<int> ms;
for (int i = 0; i < n; i++) {
    int t;
    cin >> t;
    ms.insert(t);
}
int q;
cin >> q;
while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
        int x;
        cin >> x;
        ms.insert(x);
    } else if (t == 2) {
        int x;
        cin >> x;
        ms.erase(ms.find(x));
    } else {
        int x;
        cin >> x;
        long long cnt = 0;
        for (auto a: ms) {
            for (auto b: ms) {
                cnt += (a / b) == x;
            }
        }
        cout << cnt << endl;
    }
}

Time complexity: $O (q n^{2} l o g (n))$ O(qn^2log(n)), or $O (q * n^{2})$ O(q*n^2) using hashmap like multiset

Group 2: $a_{i} \leq 1000$ a_i \leq 1000, in each query $x \leq 1000$ x \leq 1000

In this group we can notice that the number of different elements is not so big $(\leq 1000)$ (\leq 1000) so let's maintain an array $c n t_{x}$ cnt_x - which will store the number of occurrences of $x$ . Let's notice that from $⌊ \frac{p}{q} ⌋ = x$ \lfloor\frac{p}{q}\rfloor = x goes $p = x q + a, a < q$ p = xq + a, a < q so the good $p$ for our $q$ are the numbers on a segment $[q x, q (x + 1) - 1]$ [qx,q(x+1)-1]. So now we can iterate through each $q$ and add to our answer the number of such elements $y$ that $y \in [q x, q (x + 1) - 1]$ y \in [qx,q(x+1)-1] so it is just $\sum_{i = q x}^{q (x + 1) - 1} c n t_{i}$ \sum_{i=qx}^{q(x+1)-1} cnt_i. To achieve it, we can use either Segment Tree, or Binary-Indexed Tree, or just after each query of 1st and 2nd type recalculate prefix sums.

Time complexity: $O (q * ma x_{x})$ O(q*max_x)

Memory complexity: $O (ma x_{x})$ O(max_x)

Group 3,4: There are no queries of the $2$ -nd type

For this and all the following groups, we need to notice the next fact:

if $⌊ \frac{p}{q} ⌋ = x$ \lfloor\frac{p}{q}\rfloor = x, then either $q \leq p$ q \leq \sqrt p or $x \leq p$ x \leq \sqrt p.

Let's call the biggest $q$ as $C$ . So for the solution, we will consider these two cases separately.

For $x \geq C$ x \geq \sqrt C we already know that $q \leq C$ q \leq \sqrt C so we can simply solve it as previous group.

Now, for $x \leq C$ x \leq \sqrt C first observation would be that the number of such $x$ 's is not so big $(C)$ (\sqrt C). Let's store additional array $c n t_{x}$ cnt_x which will represent the answer for small $x$ . So the question is, how can we maintain it? It turns out that it is not so hard. Assume that we have got query with insertion an element $y$ . Now we have two options. 1st is $⌊ \frac{p}{y} ⌋ = x$ \lfloor\frac{p}{y}\rfloor = x, 2nd is $⌊ \frac{y}{q} ⌋ = x$ \lfloor\frac{y}{q}\rfloor = x. Both of this variation could be calculated for each $x$ in at most $O (l o g (n))$ O(log(n)) using some data structure like Segment Tree, or Binary-Indexed Tree.

Time complexity: $O (q * C l o g (n)$ O(q*\sqrt C log(n)

Memory complexity: $O (ma x_{x})$ O(max_x)

Group 5 Here we should do it in both ways really carefully. Also the problem could be solved faster without extra log, because an update query we will perform only $O (n)$ times, and get query $O (n n)$ O(n\sqrt n). So it would be nice for us to answer update query in $O (n)$ O(\sqrt n) and get in $O (1)$ . It could be done using sqrt decomposition.

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
 
 
#include <iostream>
#include <vector>
#include <cstring>
 
 
using namespace std;
#define elif else if

 
 
const int block_size = 320;
const int max_n = 1e5 + 1;
int blocks_sum_pref[max_n / block_size + 5];
int block_pref[max_n];
 
void init() {
    memset(blocks_sum_pref, 0, sizeof(blocks_sum_pref));
    memset(block_pref, 0, sizeof(block_pref));
}
 
int bget(int l, int r) {
    if (l == (l / block_size) * block_size)
        return block_pref[r];
    return block_pref[r] - block_pref[l - 1];
}
 
int get(int l, int r) {
    if (l > r) return 0;
    int lid = l / block_size;
    int rid = r / block_size;
    if (lid == rid) {
        return bget(l, r);
    }
    int res = bget(l, (lid + 1) * block_size - 1);
    res += bget(rid * block_size, r);
    res += blocks_sum_pref[rid - 1] - blocks_sum_pref[lid];
    return res;
}
 
void add(int pos, int val) {
    int pid = pos / block_size;
    for (int i = pid; i < max_n / block_size; i++) {
        blocks_sum_pref[i] += val;
    }
    for (int i = pos; i < min(max_n, (pos / block_size + 1) * block_size); i++) {
        block_pref[i] += val;
    }
}
 
long long cnt[block_size + 5];
 
int read_int() {
    int x;
    cin >> x;
    return x;
}
 
signed main() {
    init();
    memset(cnt, 0, sizeof(cnt));
    auto insert = [&](int x) -> void {
        add(x, 1);
        int min_val;
        int max_val;
        for (int i = 1; i <= block_size; i++) {
//           a / x
 
            min_val = x * i;
            max_val = x * (i + 1) - 1;
            if (min_val >= max_n) break;
            max_val = min(max_val, max_n - 1);
            cnt[i] += get(min_val, max_val);
        }
        for (int i = 1; i <= block_size; i++) {
            //           x / a
            max_val = x / i;
            min_val = x / (i + 1) + 1;
            if (i == 1) {
                max_val--;
            }
            if (max_val == 0) break;
            if (min_val <= max_val)
                cnt[i] += get(min_val, max_val);
        }
    };
    auto erase = [&](int x) -> void {
        int min_val;
        int max_val;
        for (int i = 1; i <= block_size; i++) {
//            a / x
            min_val = x * i;
            max_val = x * (i + 1) - 1;
            if (min_val >= max_n) break;
            max_val = min(max_val, max_n - 1);
            cnt[i] -= get(min_val, max_val);
        }
        for (int i = 1; i <= block_size; i++) {
            //           x / a
            max_val = x / i;
            min_val = x / (i + 1) + 1;
            if (i == 1) {
                max_val--;
            }
            if (max_val == 0) break;
 
            if (min_val <= max_val)
                cnt[i] -= get(min_val, max_val);
        }
        add(x, -1);
    };
    auto count = [&](int x) -> long long {
        if (x <= block_size) {
            return cnt[x];
        }
        long long res = 0;
        for (int i = 1; i <= min(max_n - 1, max_n / block_size + 5); i++) {
            if (get(i, i) == 0) continue;
            int min_val = x * i;
            int max_val = min_val + i - 1;
            if (min_val >= max_n) break;
            max_val = min(max_val, max_n - 1);
            res += get(min_val, max_val) * get(i, i);
        }
        return res;
    };
 
    int n = read_int();
    for (int i = 0; i < n; i++) {
        insert(read_int());
    }
    int q;
    cin >> q;
    int t, x;
    while (q--) {
        t = read_int();
        x = read_int();
        if (t == 1) {
            insert(x);
        } elif (t == 2) {
            erase(x);
        } else {
            cout << count(x) << endl;
        }
    }
}