Roy və xəzinə qutuları#5071

Roy və xəzinə qutuları (Həll təhlili)

Massiv - sayğac $c n t$ yaradırıq. Hər bir sorğu $[l, r]$ [l, r] üçün iki əməliyyat edir: $c n t [l] + +$ cnt[l]++ və $c n t [r + 1] - -$ cnt[r + 1]--. Beləliklə, qismən cəmi $j = 1 \sum i c n t [j]$ \displaystyle\sum_{j = 1}^i cnt[j] $i$ -ci pul qutusundakı sikkələrin sayına bərabər olacaq.

Royun hərəkət etdiyi günlərin sayı $1 0^{6}$ 10^6-ı keçmir. Hər bir gün o, hər bir pul qutusuna ən çox bir sikkə qoyur. Bütün əməliyyatların tamamlanmasından sonra hər bir pul qutusunda ən çox $1 0^{6}$ 10^6 sikkə olacaq. $1 0^{6}$ 10^6 ölçüdə $co in s$ massivi yaradırıq və $co in s [i]$ -yə $i$ cəmli pul qutularının sayını daxil edirik. Bunun üçün hər bir qismən cəm üçün $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]++ edəcəyik.

Ən azı $x$ sikkə ehtiva edən pul qutularının sayını hesablayırıq. Bunun üçün $co in s$ massivində qismən cəmləri sağdan sola doğru hesablayırıq (yəni sondan). Beləliklə, ən azı $x$ sikkə ehtiva edən pul qutularının sayı $co in s [x]$ -a bərabər olacaq.

Nümunə

Pul qutularına sikkələrin belə paylanmasını alırıq:

$s$ cəmli pul qutularının sayı. Qismən cəmlər (sağdan sola hesablama) ən az $s$ sikkəni ehtiva edən pul qutularının sayını göstərir.

$0$ cəmli bir pul qutusu var (nömrə $7$ -ci pul qutusu), $1$ cəmli iki pul qutusu var (nömrə $4$ və $6$ -ci pul qutuları), $2$ cəmli üç pul qutusu var (nömrə $1, 3$ və $5$ -ci pul qutuları), $3$ cəmli bir pul qutusu var (nömrə $2$ -ci pul qutusu).

Coins massivinin qismən cəmlərini hesablayaraq təsdiqləyə bilərik ki, məsələn, ən azı $1$ sikkəni ehtiva edən $6$ pul qutusu var. Və ya ən azı $2$ sikkəni ehtiva edən $4$ pul qutusu var.

Alqoritmin həyata keçirilməsi

İşçi massivləri elan edək.

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

Giriş məlumatlarını oxuyuruq. $c n t$ massivini qururuq.

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

$s u m$ dəyişənində $c n t$ massivinin qismən cəmlərini hesablayırıq. $i$ -ci qismən cəm $i$ -ci pul qutusundakı sikkələrin sayına bərabərdir. $co in s [i]$ $i$ cəmli pul qutularının sayına bərabərdir.

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

$co in s$ massivində qismən cəmləri sağdan sola yenidən hesablayırıq.

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

Sorğuların sayını $q$ oxuyuruq. Hər bir sorğu üçün $x$ dəyərini oxuyuruq və $co in s [x]$ cavabını veririk.

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

Python ilə həyata keçirilməsi

İşçi siyahılar elan edək.

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

Giriş məlumatlarını oxuyuruq.

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

$c n t$ siyahısını qururuq.

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

$s u m$ dəyişənində $c n t$ siyahısının qismən cəmlərini hesablayırıq. $i$ -ci qismən cəm $i$ -ci pul qutusundakı sikkələrin sayına bərabərdir. $co in s [i]$ $i$ cəmli pul qutularının sayına bərabərdir.

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

$co in s$ massivinin qismən cəmlərini sağdan sola yenidən hesablayırıq.

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

Sorğuların sayını $q$ oxuyuruq. Hər bir sorğu üçün $x$ dəyərini oxuyuruq və $co in s [x]$ cavabını veririk.

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