8. A čo tak viac Torty?

Určite si pamätáte úlohu Organizácia Kapustnice z minulej série. Keď ju Kristína úspešne vyriešila na plný počet hneď sa išla svojím riešením pochváliť svojej sestričke Janke. Vysvetľovala jej ho na príklade zo zadania. Tá sa jej však začala pýtať veľa rôznych otázok: a čo keby v tomto reťazci bolo tuto T namiesto V? Ako by sa zmenilo riešenie keby sme uvažovali len tento podreťazec? Čo keby sme tu pridali V ako 3tie písmenko? Čo keby sme tu zobrali tento podreťazec a zrkadlovo ho otočili?

Úloha

Naštudujte si úlohu Organizácia Kapustnice z minulej série. V nej začneme so stolom s vedúcimi a tortami – reprezentovaný reťazcom z písmen ‘T’ - reprezentujúce tortu, a ‘V’ – reprezentujúce vedúceho. Vedúci sa hýbu zľava doprava, zoberú prvú tortu ku ktorej prídu a odídu z radu. Chceme doniesť do radu niekoľko vedúcich a/alebo tort, tak aby každá torta bola zjedená, a každý vedúci mal presne jednu tortu, a to tak, aby výsledný rad (počet vedúcich + počet tort) bol čo najmenší. Práve dĺžka najmenšieho radu ktorý vieme dostať, je čo nás zaujíma.

Navyše, chceme vedieť, ako sa táto hodnota mení, ak zmeníme rad vedúcich a tort. Na vstupe bude postupne \(q\) z nasledovných požiadaviek:

1. vysledok a b - vypíšte najmenšiu dosiahnuteľnú dĺžku opraveného radu, ak nás zaujíma rad medzi reprezentovaný tortami/vedúcimi medzi indexami \(a\) a \(b\) – vrátane. (Indexy číslujeme od 0.) Napriklad ak je momentálne stav radu VVTVTTVV a chceme vyhodnotiť operáciu vysledok 1 5, tak program vypíše 6, pretože to je dĺžka správneho výsledku úlohy keď sa uvažuje podreťazec VTVTT začínajúci na indexe \(1\) a končiaci na indexe \(5\).

2. vymen a z - zmeňte znak na pozícii \(a\) na znak z. z je buď ‘V’ alebo ‘T’. Napríklad reťazec VVTVTTVV sa operáciou vymen 1 T zmení na VTTVTTVV.

3. pridaj a z - pridaj na \(a\)-te miesto radu (teda po \(a\) miestach v rade) bude pridaný znak z (vedúci ak je to ‘V’, torta ak ‘T’). Napríklad reťazec VTTVTTVV sa operáciou pridaj 2 V zmení na VTVTVTTVV.

4. zmaz a b - z radu odstránime všetkých vedúcich/všetky torty medzi indexami \(a\) a \(b\) (vrátane). Napríklad reťazec VTVTVTTVV sa operáciou zmaz 5 6 zmení na VTVTVVV.

5. reverzni a b - zrkadlovo obrátime časť radu medzi indexami \(a\) a \(b\). Napríklad reťazec VTVTVVV sa operáciou reverzni 1 4 zmení na VVTVTVV.

Vstup

V prvom riadku vstupu sú dve čísla: Počet znakov v počiatočnom reťazci \(1 \le n \le 10^5\) a počet operácii \(0 \le q \le 10^5\). Na druhom riadku vstupu sa nachádza počiatočný stav radu \(r\). Nasledujúcich \(q\) riadkov popisuje operácie. Každý z týchto riadkov obsahuje jedno z nasledujúcich:

1. vysledok a b kde \(0 \le a \le b\) a \(b\) je menej ako dĺžka reťazca vytvoreného predchádzajúcimi operáciami

2. vymen a z kde \(0 \le a\), \(z\in\{V, T\}\) a \(a\) je menej ako dĺžka reťazca vytvoreného predchádzajúcimi operáciami

3. pridaj a z kde \(0 \le a\), \(z\in\{V, T\}\) a \(a\) nepresiahne dĺžku reťazca vytvoreného predchádzajúcimi operáciami

4. zmaz a b kde \(0 \le a \le b\) a \(b\) je menej ako dĺžka reťazca vytvoreného predchádzajúcimi operáciami

5. reverzni a b kde \(0 \le a \le b\) a \(b\) je menej ako dĺžka reťazca vytvoreného predchádzajúcimi operáciami

Výstup:

Pre každú operáciu vysledok a b vypíšte jedno číslo: najmenšiu možnú dĺžku na ktorú možno “opraviť” podreťazec radu medzi indexami \(a\) a \(b\) (vrátane).

Bodovanie

Existuje 8 testovacích sád.

• V prvej sade počet operácii \(q \le 100\) a dĺžka reťazca neprekročí 100.

• V druhej sade bude používaná iba operácia vysledok na celom vstupe, a operácia pridaj ale nové torty/vedúci sú pridané iba na koniec radu

• V tretej sade bude používaná iba operácia vysledok ale na ľubovolnom podintervale.

• V sadách 4, 5 budú používané iba operácie vymen a vysledok.

• V sade 6 budú požívané iba operácie vymen, vysledok, pridaj.

• V sade 7 budú používané operácie vymen, vysledok, pridaj a zmaz.

• V sade 8 budú používané všetky operácie.

Príklad

Input:

8 9
VVTVTTVV
vysledok 1 5
vymen 1 T
vysledok 1 5
pridaj 2 V
vysledok 1 5
zmaz 5 6
vysledok 1 5
reverzni 1 4
vysledok 1 5

Output:

6
8
6
8
6

• Prvá otázka sa pýta na najlepšie opravenie (pod)radu VTVTT. Z riešenia Organizácie Kapustnice vieme, že výsledok je 6.
• Po druhej požiadavke bude rad VTTVTTVV.
• Tretia otázka sa pýta na opravenie radu TTVTT, z ktorého najlepšie vieme spraviť napríklad VVVTTVTT.
• Po štvrtej požiadavke bude rad VTVTVTTVV.
• Piata otázka sa pýta na opravenie radu TVTVT, do ktorého stačí pridať jediného vedúceho.
• Po šiestej požiadavke dostaneme rad VTVTVVV.
• Siedma otázka sa pýta na podpostupnosť TVTVV.
• Po ôsmej požiadavke dostaneme rad VVTVTVV.
• Napokon, deviata otázka sa pýta na odpoveď pre podpostupnosť VTVTV.