Urmașii lui Moisil 2023 - Clasele XI-XII - Mirror | perioade

This was the problem page during the contest. Access the current page here.
Time limit: 3s Memory limit: 128MB Input: perioade.in Output: perioade.out

De ziua lui, Florin a primit un șir de caractere periodic și infinit. Perioada lui are lungime nn și conține doar litere mici ale alfabetului englez.

Deoarece este curios, el vrea să își personalizeze șirul primit în diverse moduri. Pentru a face asta, el vă dă qq operații care se realizează pe șirul dat, operații de două tipuri, după cum urmează:

  • 1 x y: Litera de pe poziția xx devine egală cu yy, unde yy este o literă mică a alfabetului englez.
  • 2 a b c: Florin vrea să afle câte litere egale cu cc există între pozițiile [a,b][a, b] din șirul de caractere.

Fiindcă nu vrea să strice periodicitatea șirului foarte mult, Florin vă garantează că pentru toate operațiile de actualizare, valorile pozițiilor modificate au în reprezentarea binară cel mult kk biți egali cu 11.

Cerință

Scrieţi un program care, dându-se șirul de caractere și actualizările, răspunde la interogări.

Date de intrare

Fişierul de intrare perioade.in conține pe prima linie nn și kk, reprezentând lungimea perioadei șirului de caractere, respectiv numărul maxim de biți de 11 pe care îl are o poziție modificată la operația de tipul 11.

Pe cea de-a doua linie se va citi perioada șirului de caractere inițial.

Pe cea de-a treia linie se va citi qq, reprezentând numărul de operații făcut de Florin.

Pe următoarele qq linii se vor citi operațiile, care respectă descrierea din enunț.

Date de ieșire

Fişierul de intrare perioade.out va conține răspunsurile pentru operațiile de tipul 22, câte un răspuns pe fiecare linie, în ordinea în care sunt date în datele de intrare.

Restricții și precizări

  • 1n,q250 0001 \leq n, q \leq 250 \ 000;
  • 1k41 \leq k \leq 4;
  • Pentru toate query-urile, 1x,a,b10181 \le x, a, b \le 10^{18}, aba \le b. Pozițiile modificate au cel mult kk biți egali cu 11;
  • Pentru 1414 puncte, 1n,q2 0001 \le n, q \le 2 \ 000 și 1poz4 0001 \le poz \le 4 \ 000;
  • Pentru 2525 de puncte, k2k \le 2, n,q105n, q \le 10^5;
  • Pentru 1414 puncte, 1poz21051 \le poz \le 2 * 10^{5};
  • Pentru 4747 de puncte, nu există restricții suplimentare.

Exemplu

perioade.in

3 4
bun
11
1 9 a
1 7 a
2 3 11 n
1 4 x
2 7 13 b
1 6 o
1 12 b
1 8 r
2 1 15 u
1 7 b
2 3 12 b

perioade.out

2
2
4
3

Explicație

  • Înainte de operații, șirul este bunbunbunbunbunbun...
  • După primele două actualizări, șirul devine bunbunauabunbunbun...
  • Pentru prima operație de tipul 22, avem litera nn pe pozițiile 33 și 66.
  • După următoarea actualizare, șirul devine bunxunauabunbunbun...
  • Pentru cea de-a doua operație de tipul 22, vom avea litera bb pe pozițiile 1010 și 1313.
  • După următoarele trei actualizări, șirul devine bunxuoarabubbunbun...
  • Pentru cea de-a treia operație de tipul 22, vom avea litera uu pe pozițiile 22, 55, 1111 și 1414.
  • După următoarea actualizare, șirul devine bunxuobrabubbunbun...
  • Pentru ultima operație de tipul 22, vom avea litera bb pe pozițiile 77, 1010 și 1212.

Log in or sign up to be able to send submissions!