1. Идея

Нужно для каждого IPv4-адреса посчитать, скольким из заданных CIDR-блоков он принадлежит.

Прямая проверка каждого адреса по всем подсетям дала бы O(nq), что при n, q <= 10^5 слишком медленно.

Ключевая идея: подсеть a.b.c.d/p определяется только длиной префикса p и значением первых p битов адреса. Значит, все подсети можно сгруппировать по парам:

• длина префикса p,
• сам префикс длины p.

Тогда для каждого запроса-адреса достаточно перебрать все возможные длины префикса от 0 до 32, вычислить его префикс такой длины и посмотреть, сколько подсетей с таким префиксом было во входных данных.

Так как длин префикса всего 33, один запрос обрабатывается очень быстро.

2. Наблюдения

Наблюдение 1. IPv4 удобно хранить как 32-битное число

Адрес a.b.c.d можно превратить в одно число:

• a — старший байт,
• d — младший байт.

То есть:

ip = (a << 24) | (b << 16) | (c << 8) | d

После этого первые p битов адреса удобно получать сдвигом вправо на 32 - p.

Например, если p = 24, то:

• ip >> 8 — это и есть 24-битный префикс.

Наблюдение 2. Что значит принадлежность подсети

Адрес принадлежит подсети a.b.c.d/p, если первые p битов у адреса и у сети совпадают.

Если представить и адрес сети, и проверяемый IP как 32-битные числа, то условие сводится к равенству префиксов длины p.

То есть адрес x принадлежит подсети (net, p), если:

• при p = 0 — всегда принадлежит,
• иначе x >> (32 - p) == net >> (32 - p).

Наблюдение 3. Дубликаты подсетей возможны

Если одна и та же подсеть встречается несколько раз, то она должна учитываться несколько раз. Поэтому нужно не просто хранить факт существования префикса, а считать количество таких подсетей.

Наблюдение 4. Перебирать все p от 0 до 32 — это нормально

Всего длина префикса может быть только одной из 33 величин. Значит, на каждый запрос достаточно 33 проверок.

Итоговая асимптотика получится порядка O(n + 33q), что легко проходит.

3. Алгоритм

Шаг 1. Научиться разбирать IPv4-адрес

Преобразуем строку вида a.b.c.d в одно число.

Например, для 1.2.3.4 получим:

• 1 << 24
• 2 << 16
• 3 << 8
• 4

и сложим побитовым |.

Шаг 2. Считать все подсети

Для каждой строки вида a.b.c.d/p:

1. отделяем часть адреса и число p;
2. преобразуем адрес в 32-битное число ip;
3. вычисляем его префикс длины p:
   • если p = 0, то префикс считаем равным 0;
   • иначе prefix = ip >> (32 - p);
4. увеличиваем счётчик для пары (p, prefix).

В C++ в эталонном решении эта пара упакована в одно число key. В Python используется кортеж (p, prefix).

Шаг 3. Ответить на запросы

Для каждого IP-адреса:

1. преобразуем его в число ip;
2. заводим ans = 0;
3. для всех p от 0 до 32:
   • вычисляем префикс длины p;
   • добавляем к ответу количество подсетей с таким (p, prefix);
4. выводим ans.

4. Почему это работает

Докажем, что алгоритм считает ответ правильно.

Рассмотрим некоторую подсеть a.b.c.d/p.

После обработки входа она добавляет 1 к счётчику для пары:

• длина префикса p,
• значение первых p битов её адреса.

Теперь рассмотрим запросный IP-адрес x.

Во время обработки запроса мы перебираем все p от 0 до 32. Для конкретного p вычисляем первые p битов адреса x и смотрим, сколько подсетей имеют такой же префикс.

Подсеть a.b.c.d/p будет учтена в ответе тогда и только тогда, когда:

• длина совпадает: рассматривается именно это p,
• префикс длины p у x совпадает с префиксом длины p у адреса сети.

А это в точности и означает, что адрес x принадлежит подсети a.b.c.d/p.

Каждая подсеть учитывается ровно один раз — на своей длине префикса p. Если одинаковая подсеть встречается несколько раз, её счётчик увеличен несколько раз, и все вхождения тоже будут правильно учтены.

Значит, итоговая сумма по всем p равна количеству заданных подсетей, содержащих данный адрес.

5. Сложность

Пусть:

• n — число подсетей,
• q — число запросов.

Тогда:

• обработка всех подсетей: O(n),
• обработка одного запроса: O(33),
• обработка всех запросов: O(33q).

Итого:

• время: O(n + 33q), что эквивалентно O(n + q),
• память: O(n) в худшем случае для хранения разных префиксов.

6. Код на C++17

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

long long parse_ip(const string& s) {
    long long parts[4] = {0, 0, 0, 0};
    int idx = 0;
    long long cur = 0;
    for (char c : s) {
        if (c == '.') {
            parts[idx++] = cur;
            cur = 0;
        } else {
            cur = cur * 10 + (c - '0');
        }
    }
    parts[idx] = cur;
    return (parts[0] << 24) | (parts[1] << 16) | (parts[2] << 8) | parts[3];
}

int main() {
    int n, q;
    cin >> n >> q;

    unordered_map<long long, int> cnt;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        int slash_pos = -1;
        for (int j = 0; j < (int)s.size(); j++) {
            if (s[j] == '/') {
                slash_pos = j;
                break;
            }
        }

        string ip_part = s.substr(0, slash_pos);
        string p_part = s.substr(slash_pos + 1);

        int p = 0;
        for (char c : p_part) {
            p = p * 10 + (c - '0');
        }

        long long ip = parse_ip(ip_part);
        long long prefix;
        if (p == 0) {
            prefix = 0;
        } else {
            prefix = ip >> (32 - p);
        }

        long long key = ((long long)p << 32) | prefix;
        cnt[key]++;
    }

    for (int i = 0; i < q; i++) {
        string s;
        cin >> s;
        long long ip = parse_ip(s);

        long long ans = 0;
        for (int p = 0; p <= 32; p++) {
            long long prefix;
            if (p == 0) {
                prefix = 0;
            } else {
                prefix = ip >> (32 - p);
            }
            long long key = ((long long)p << 32) | prefix;
            auto it = cnt.find(key);
            if (it != cnt.end()) {
                ans += it->second;
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

7. Код на Python 3

n, q = map(int, input().split())

def parse_ip(s):
    parts = s.split('.')
    return ((int(parts[0]) << 24) |
            (int(parts[1]) << 16) |
            (int(parts[2]) << 8) |
            int(parts[3]))

cnt = {}

for _ in range(n):
    s = input().strip()
    ip_part, p_part = s.split('/')
    p = int(p_part)
    ip = parse_ip(ip_part)
    if p == 0:
        prefix = 0
    else:
        prefix = ip >> (32 - p)
    key = (p, prefix)
    cnt[key] = cnt.get(key, 0) + 1

for _ in range(q):
    s = input().strip()
    ip = parse_ip(s)
    ans = 0
    for p in range(33):
        if p == 0:
            prefix = 0
        else:
            prefix = ip >> (32 - p)
        ans += cnt.get((p, prefix), 0)
    print(ans)