Sorğuların sayı
Verilmiş iki tam ədəd n və k. idx zirvəsindən [l, r] massivinin seqmentinə uyğun gələn seqment ağacı ilə [from, to] sorğusunun işlənməsi funksiyasını nəzərdən keçirək (from ≤ to, l ≤ r).
int get (int idx, int l, int r, int from, int to ) {
int ans = 1;
if (l == from r == to)
return ans ;
int mid = ( l + r ) / 2;
if (from <= mid)
ans += get ( 2 * idx + 1, l, mid, from, min (mid, to));
if (to >= mid + 1 )
ans += get ( 2 * idx + 2, mid + 1, r, max (from, mid + 1), to) ;
return ans ;
}
get(0, 0, n-1, from, to) funksiyasının cavab olaraq k qaytardığı [from, to] (0 ≤ from ≤ to ≤ n-1) sorğularının sayını tapmaq lazımdır. Cavabı 10^9 + 9 modulu ilə çıxarın.
Giriş verilənləri
Birinci sətirdə boşluqla ayrılmış iki tam ədəd verilir: n (1 ≤ n ≤ 10^18), k (0 ≤ k ≤ 10^18).
Çıxış verilənləri
Bir tam ədəd çıxarın — məsələnin cavabı 1000000009 (10^9 + 9).