Рой і скарбнички#5071

Рой і скарбнички (Розбір)

Заведемо масив — лічильник $c n t$ . Для кожного запиту $[l, r]$ [l, r] виконаємо дві операції: $c n t [l] + +$ cnt[l]++ та $c n t [r + 1] - -$ cnt[r + 1]--. Таким чином, часткова сума $j = 1 \sum i c n t [j]$ \displaystyle\sum_{j = 1}^i cnt[j] буде дорівнювати кількості монет у $i$ -й скарбничці.

Кількість днів, у які Рой здійснює дії, не перевищує $1 0^{6}$ 10^6. Кожен день він кладе в кожну скарбничку не більше однієї монети. Після виконання всіх дій у кожній скарбничці буде знаходитись не більше $1 0^{6}$ 10^6 монет. Заведемо масив $co in s$ розміру $1 0^{6}$ 10^6 і внесемо в $co in s [i]$ кількість скарбничок із сумою $i$ . Для цього для кожної часткової суми $s u m = j = 1 \sum i c n t [j]$ sum = \displaystyle\sum_{j = 1}^i cnt[j] покладемо $co in s [s u m] + +$ coins[sum]++.

Обчислимо кількість скарбничок, які містять як мінімум $x$ монет. Для цього в масиві $co in s$ перераховуємо його часткові суми справа наліво (тобто з кінця). Тоді кількість скарбничок, які містять як мінімум $x$ монет, буде дорівнювати $co in s [x]$ .

Приклад

Отримаємо наступний розподіл монет по скарбничках:

Кількість скарбничок із сумою $s$ . Часткові суми (підраховані справа наліво) містять кількість скарбничок, які містять як мінімум $s$ монет.

Є одна скарбничка із сумою $0$ (скарбничка номер $7$ ), дві скарбнички із сумою $1$ (скарбнички номер $4$ і $6$ ), три скарбнички із сумою $2$ (скарбнички номер $1, 3$ і $5$ ), одна скарбничка із сумою $3$ (скарбничка номер $2$ ).

Обчисливши часткові суми масиву $co in s$ , можна стверджувати, наприклад, що існує $6$ скарбничок, які містять як мінімум $1$ монету. Або що існує $4$ скарбнички, які містять як мінімум $2$ монети.

Реалізація алгоритму

Оголосимо робочі масиви.

#define MAX 1000010
int cnt[MAX], coins[MAX];

Читаємо вхідні дані. Будуємо масив $c n t$ .

scanf("%d %d",&n,&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d",&l,&r);
  cnt[l]++; cnt[r+1]--;
}

У змінній $s u m$ підраховуємо часткові суми масиву $c n t$ . $i$ -а часткова сума дорівнює кількості монет у $i$ -й скарбничці. $co in s [i]$ дорівнює кількості скарбничок із сумою $i$ .

sum = 0;
for(i = 1; i <= n; i++)
{
  sum += cnt[i];
  coins[sum]++;
}

У масиві $co in s$ перераховуємо його часткові суми справа наліво.

for(i = MAX - 2; i >= 0; i--)
  coins[i] += coins[i+1];

Читаємо кількість запитів $q$ . Для кожного запиту читаємо значення $x$ і виводимо відповідь $co in s [x]$ .

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d",&x);
  printf("%d\n",coins[x]);
}

Python реалізація

Оголосимо робочі списки.

MAX = 1000010
cnt = [0] * MAX
coins = [0] * MAX

Читаємо вхідні дані.

n = int(input())
m = int(input())

Будуємо список $c n t$ .

for _ in range(m):
  l, r = map(int, input().split())
  cnt[l] += 1
  cnt[r + 1] -= 1

У змінній $s u m$ підраховуємо часткові суми списку $c n t$ . $i$ -а часткова сума дорівнює кількості монет у $i$ -й скарбничці. $co in s [i]$ дорівнює кількості скарбничок із сумою $i$ .

sum = 0
for i in range(1, n + 1):
  sum += cnt[i]
  coins[sum] += 1

У масиві $co in s$ перераховуємо його часткові суми справа наліво.

for i in range(MAX - 2, -1, -1):
  coins[i] += coins[i + 1]

Читаємо кількість запитів $q$ . Для кожного запиту читаємо значення $x$ і виводимо відповідь $co in s [x]$ .

q = int(input())
for _ in range(q):
  x = int(input())
  print(coins[x])