Valentine and Queries
All submissions for this problem are available.
Valentines is coming after Q days and Tappu desperately needs to impress his girlfriend Kannu.
In order to test the extent of Tappu's love for her, Kannu gives Tappu a string S[1.....N] of length N .
On the i th day of the Q days, she asks him about the number of substrings in the string S[Li...Ri] (both inclusive) which are same when read in forward as well as backward direction. (S[Li.....Ri] denotes the substring of S from index Li to Ri)
If the answer of the i - 1 th day was A, Li and Ri for the i th day changes according to the following formula:
where K1 and K2 are constants.
She gives Tappu L1 and R1 for the 1st day.
Tappu being a little slow in calculations asks for your help.
Would you help him impress his valentine?
First line contains the length of string N and the next line contains the string S.
The subsequent line contains the number of queries Q, L1, R1, K1 and K2 respectively.
The indexing of Li and Ri is 1-based.
Output Q lines each containing the answer for the i th day.
Input: 5 ababc 2 1 3 7 12 Output: 4 5
L1 = 1 and R1 = 3
so here the substring is "aba" and the 4 palindromes are "a", "b", "a", "aba".
Using A = 4,
we get L2 = (4 * 1 + 10) % 5 + 1 = 5
and R2 = (4 * 3 + 15) % 5 + 1 = 2,
here L > R so after swapping, L2 = 2 and R2 = 5
so here the resulting substring becomes "babc" and the no. of palindromes is 5 which are "b", "a", "b", "c", "bab".
|Time Limit:||1 - 2.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.