7. Ye ti zima? vzorové riešenie

16
kkssppkokosplesk
4
6 15
4 14
3 3
15 0

2
8
0
16

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)\).

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;

    vector<long long> prefixK(N+1,0), prefixS(N+1,0), prefixP(N+1,0);
    for (int n=0; n<N; ++n) prefixK[n+1] = prefixK[n] + (S[n] == 'k');
    for (int n=0; n<N; ++n) prefixS[n+1] = prefixS[n] + (S[n] == 's');
    for (int n=0; n<N; ++n) prefixP[n+1] = prefixP[n] + (S[n] == 'p');

    vector<long long> prefixKS(N+1,0), prefixSP(N+1,0);
    for (int n=0; n<N; ++n) prefixKS[n+1] = prefixKS[n] + (S[n] == 's')*prefixK[n];
    for (int n=0; n<N; ++n) prefixSP[n+1] = prefixSP[n] + (S[n] == 'p')*prefixS[n];
    
    vector<long long> prefixKSP(N+1,0);
    for (int n=0; n<N; ++n) prefixKSP[n+1] = prefixKSP[n] + (S[n] == 'p')*prefixKS[n];

    int Q;
    cin >> Q;
    vector<long long> C(Q,0);
    for (int q=0; q<Q; ++q) {
        int x, y;
        cin >> x >> y;
        if (q > 0) { x = (x+C[q-1])%N; y = (y+C[q-1])%N; }
        int a = min(x,y), b = max(x,y)+1;

        long long SP_in_ab = prefixSP[b];
        SP_in_ab -= prefixSP[a];
        SP_in_ab -= prefixS[a] * (prefixP[b] - prefixP[a]);

        C[q] = prefixKSP[b];
        C[q] -= prefixKSP[a];
        C[q] -= prefixKS[a] * (prefixP[b] - prefixP[a]);
        C[q] -= prefixK[a] * SP_in_ab;

        cout << C[q] << "\n";
    }
}