Zadanie

Yeti Ignác nedávno dostal skvelý nápad: oholí si nohy, aby bol krajší. No len čo tak spravil, pochopil, že ten nápad nebol až taký skvelý. Keď sa teraz brodí snehom, je mu zima. Rozhodol sa preto, že si pustí na počítači vaše programy a tým sa zahreje.

Vytrestajte Ignáca za jeho hlúpe nápady, nech si dobre zapamätá, že yeti si nemá holiť nohy. Vyriešte teda čo najefektívnejšie nasledujúcu úlohu, nech sa yeti príliš nezahreje.

Úloha

KSP-krása reťazca je počet spôsobov, ktorými v ňom vieme vyznačiť podpostupnosť ksp – teda niekde vyznačiť písmeno k, niekde napravo od neho písmeno s a napravo od toho zase písmeno p. Napríklad KSP-krása reťazca kokosplesk je 2: buď zoberieme znaky na indexoch 0, 4, 5 alebo znaky na indexoch 2, 4, 5.

Na vstupe dostanete jeden reťazec \(S\) a potom postupne \(q\) otázok o ňom. Každá otázka bude nasledujúceho tvaru: “Aká je KSP-krása podreťazca tvoreného znakmi na indexoch \(a_i\)\(b_i\)?”

Formát vstupu

V prvom riadku je číslo \(n\): dĺžka reťazca. V druhom riadku je reťazec \(S\) tvorený \(n\) malými písmenami anglickej abecedy. V treťom riadku je číslo \(q\): počet otázok.

Zvyšok vstupu tvorí \(q\) riadkov. Tieto riadky a aj im zodpovedajúce otázky si očíslujeme od 0 po \(q-1\). Správnu odpoveď na otázku \(i\) označíme \(c_i\) a navyše dodefinujeme, že \(c_{(-1)} = 0\).

Riadok popisujúci otázku číslo \(i\) obsahuje dve celé čísla \(x_i\) a \(y_i\), pre ktoré platí \(0\leq x_i, y_i < n\). Hodnoty \(a_i\) a \(b_i\) pre túto otázku sú určené nasledovne: Nech \(p_i = (x_i + c_{i-1}) \bmod n\) a \(q_i = (y_i + c_{i-1}) \bmod n\). Potom \(a_i = \min(p_i,q_i)\) a \(b_i = \max(p_i,q_i)\).

V jednotlivých sadách testov platia pre \(n\) a \(q\) nasledovné obmedzenia zhora:

Sada 1 2 3 4
\(n,q\) 50 \(20\,000\) \(100\,000\) \(500\,000\)

Formát výstupu

Vypíšte \(q\) riadkov a v nich postupne čísla \(c_0\)\(c_{q-1}\).

Upozornenie

Pri hodnotení popisov budeme o čosi viac ako inde prihliadať na asymptotickú časovú zložitosť vašich riešení. Špeciálne upozorňujeme na to, že algoritmy asymptoticky horšie od vzorového riešenia nedostanú plný počet bodov za popis (hoci môžu úspešne vyriešiť všetky testy).

Príklad

Input:

16
kkssppkokosplesk
4
6 15
4 14
3 3
15 0

Output:

2
8
0
16
  • Otázka 0 sa pýta na podreťazec kokosplesk, ktorého KSP-krása je \(c_0 = 2\).
  • Keď vieme, že \(c_0=2\), vypočítame si, že otázka 1 má \(a_1=0\) a \(b_1=6\), pýta sa teda na reťazec kkssppk. Toto KSP-krása je \(c_1 = 8\).
  • Otázka 2 sa pýta na nejaký jednoznakový reťazec, toho KSP-krása je určite \(c_2 = 0\).
  • No a na záver, otázka 3 sa teda pýta na celý reťazec \(S\).

Táto úloha mala až prekvapivo jednoduché riešenie. Netreba žiadne logaritmické dátové štruktúry, vystačíme si s obyčajnými prefixovými súčtami a každú otázku zodpovieme v konštantnom čase.

Skôr, než sa do riešenia pustíme, dohodneme sa, že všetky intervaly, ktoré budeme používať, budú polootvorené: ľavý koniec do nich patrí, pravý už nie. Napr. \([0,3)\) je interval obsahujúci čísla 0, 1 a 2, zatiaľ čo \([4,5)\) obsahuje len číslo 4.

Základná myšlienka riešenia bude nasledovná: keď máme zistiť počet spôsobov, ako vybrať reťazec ‘ksp’ zo znakov, ktorých indexy ležia v intervale \([a,b)\), zoberieme počet spôsobov, ako vybrať ‘ksp’ zo znakov s indexmi v intervale \([0,b)\) a od nich potom odpočítame tie zlé. Zlé spôsoby sú troch typov: buď leží v intervale \([0,a)\) len znak ‘k’, alebo znaky ‘ks’, alebo tam leží celé ‘ksp’. Nižšie si detailne popíšeme, ako všetky tieto počty v konštantnom čase vypočítať z obyčajných prefixových súčtov.

Počet spôsobov, ako vybrať reťazec \(r\) spomedzi prvých \(i\) písmen reťazca \(S\) si označíme \(P_r[i]\).

Pre jednopísmenové reťazce je tento počet veľmi ľahké spočítať: je to jednoducho počet výskytov dotyčného znaku v dotyčnom úseku reťazca \(S\). Napríklad teda platí \(P_k[0] = 0\) a \(\forall i: P_k[i+1] = P_k[i] + (1 \text{~ak~$S[i]$='k'})\). Analogicky spočítame hodnoty \(P_s\) a \(P_p\).

Pozrime sa teraz na hodnoty \(P_{ks}\). Zjavne aj tu platí \(P_{ks}[0] = 0\), lebo keď nemáme žiadne znaky, nevyberieme žiadne \(ks\). Predstavme si teraz, že postupne zväčšujeme dĺžku prefixu \(S\), z ktorého môžeme vyberať. Keď pribudne nové písmeno, sú dve možnosti. Ak to nie je ‘s’, tak sa počet spôsobov výberu ‘ks’ nijak nezmení – toto nové písmeno nemáme ako použiť. A ak pribudne ‘s’, zväčší sa počet ‘ks’ o toľko, koľko rôznych ‘k’ sme už videli. Dokopy teda dostávame toto: \(\forall i: P_{ks}[i+1] = P_{ks}[i] + (P_k[i] \text{~ak~$S[i]$='s'})\).

Rovnakým spôsobom vieme spočítať aj hodnoty \(P_{sp}\). No a úplne na záver celej prípravy si spočítame hodnoty \(P_{ksp}\), pričom znova opakujeme tú istú úvahu: ak pre nejaké \(i\) vidíme, že \(S[i]\)=‘p’, pribudlo nám do \(P_{ksp}[i+1]\) oproti \(P_{ksp}[i]\) práve toľko nových možností výberu reťazca ‘ksp’, koľko máme možností na výber ‘ks’ zo znakov s indexmi menšími ako \(i\).

Ako teraz zodpovieme na otázku, koľkými spôsobmi vieme ‘ksp’ vybrať z daného úseku \([a,b)\) reťazca \(S\)? Hľadanú odpoveď môžeme zapísať v tvare \(\alpha - \beta - \gamma - \delta\), kde:

  • \(\alpha\) je počet výskytov ‘ksp’ v intervale \([0,b)\).
  • \(\beta\) je počet výskytov ‘ksp’ v intervale \([0,a)\).
  • \(\gamma\) je počet výskytov ‘ksp’ takých, že ‘k’ leží v intervale \([0,a)\) a ‘sp’ v intervale \([a,b)\).
  • \(\delta\) je počet výskytov ‘ksp’ takých, že ‘ks’ leží v intervale \([0,a)\) a ‘p’ v intervale \([a,b)\).

Skoro všetky tieto hodnoty už vieme:

  • \(\alpha = P_{ksp}[b]\)
  • \(\beta = P_{ksp}[a]\)
  • \(\delta = P_{ks}[a] \cdot (P_p[b] - P_p[a])\). Rozmyslite si, prečo je \(P_p[b] - P_p[a]\) rovné počtu výskytov ‘p’ v \([a,b)\).

Jediné, s čím ešte bude trocha práce, je \(\gamma\). Ale tej práce bude skutočne len trocha, keďže hodnotu \(\gamma\) môžeme tiež určiť podobnou úvahou. Máme \(P_k[a]\) možností, ako vybrať ‘k’ ležiace v intervale \([0,a)\), ostáva nám už len určiť počet spôsobov, ako vybrať ‘sp’ z intervalu \([a,b)\). No a toto vieme zistiť ako \(\zeta - \eta - \theta\), kde:

  • \(\zeta\) je počet výskytov ‘sp’ v intervale \([0,b)\), teda \(\zeta = P_{sp}[b]\)
  • \(\eta\) je počet výskytov ‘sp’ v intervale \([0,a)\), teda \(\eta = P_{sp}[a]\).
  • \(\theta\) je počet výskytov ‘sp’ takých, že ‘s’ leží v \([0,a)\) a ‘p’ leží v \([a,b)\), čiže \(\theta = P_s[a]\cdot(P_p[b]-P_p[a])\).

A to už je všetko. V lineárnom čase od dĺžky \(S\) sme si predpočítali hodnoty \(P\) a následne v konštantnom čase vieme odpovedať na ľubovoľnú otázku. Celková časová zložitosť je teda \(O(n+q)\).

Zdrojové kódy budú zverejnené až po 17.6. 23:59:59. Dovtedy sa môžete pokúsiť úlohu naprogramovať sami
(a získať tým nejaké body navyše).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.