P13242 "2.48sOI R1" Your Name


Since you cannot swap bodies, you need to solve a problem. Let $\operatorname{occ}(u,v)$ be the number of occurrences of **string $\boldsymbol v$** in **string $\boldsymbol u$**. Let $t[l,r]$ denote the substring of string $t$ consisting of the $l$-th to the $r$-th characters. Given a sequence of strings $(s_1,\dots,s_n)$, a sequence of positive integers $(a_1,\dots,a_n)$, and a string $t$, there are $q$ queries. Each query has four parameters $l_1,r_1,l_2,r_2$. Compute: $$\sum\limits_{i=l_1}^{r_1}\left(\operatorname{occ}(s_i,t[l_2,r_2])\times\min\limits_{j=l_1}^{i}a_j\right)$$ For the subtask with $o=1$, you need to support online queries.

There are $n+q+3$ lines in total. - The first line contains six positive integers $\text{sid},n,q,o,L,R$. Here $\text{sid}$ indicates the Subtask ID of the test point. In particular, for the sample, $\text{sid}=0$. The meanings of the other values are as described in the statement. - Lines $2$ to $n+1$: $n$ strings $(s_1,\dots,s_n)$. - Line $n+2$: a string $t$. - Line $n+3$: $n$ positive integers $(a_1,\dots,a_n)$. - Lines $n+4$ to $n+q+3$: each line contains four positive integers $L_1,R_1,L_2,R_2$, describing a query. For the $i$-th query, let the answer to the $(i-1)$-th query be $\text{lst}$ (if $i=1$, then $\text{lst}=0$). Then $l_1,l_2,r_1,r_2$ are computed as: - $l_1=(L_1+o\times\text{lst}-1)\bmod n+1$. - $r_1=(R_1+o\times\text{lst}-1)\bmod n+1$. - $l_2=(L_2+o\times\text{lst}-1)\bmod |t|+1$. - $r_2=(R_2+o\times\text{lst}-1)\bmod |t|+1$. If $l_1>r_1$, swap $l_1,r_1$. Do the same for $l_2,r_2$. When $L\ne -1$, you need to change all $l_1$ to $L$; when $R\ne -1$, you need to change all $r_1$ to $R$ (if the initial $l_1>r_1$, this operation is performed after swapping $l_1,r_1$).

There are $q$ lines. The $i$-th line gives the result of the $i$-th query in the formal statement.

**Sample Explanation #1** Take the last query as an example: $t[7,12] = \texttt{ababaa}$. The needed $\text{occ}$ values are: - $\text{occ}(s_1,t[7,12])=\text{occ}(s_2,t[7,12])=\text{occ}(s_4,t[7,12])=\text{occ}(s_5,t[7,12])=1$. - $\text{occ}(s_3,t[7,12])=0$. So the answer is $114\times 1+51\times 1+41\times 0 + 41\times 1 + 41\times 1 = 247$. **Constraints** **This problem uses bundled testdata.** Let $m=\sum\limits_{i=1}^n\lvert s_i\rvert$. | $\text{sid}=$ | $n,m,\lvert t\rvert\le$ | $q\le$ | $a_i\le$ | $o=$ | Special Properties | Score | Subtask Dependencies | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $100$ | $100$ | $10^9$ | $0$ | | $5$ | | | $2$ | $2\times 10^5$ | $2\times 10^5$ | $10^9$ | $1$ | $\text{A}$ | $10$ | | | $3$ | $2\times 10^5$ | $2\times 10^5$ | $1$ | $1$ | | $15$ | | | $4$ | $10^4$ | $10^4$ | $10^9$ | $0$ | | $15$ | $1$ | | $5$ | $2\times 10^5$ | $2\times 10^5$ | $10^9$ | $0$ | | $20$ | $4$ | | $6$ | $2\times 10^5$ | $2\times 10^5$ | $10^9$ | $1$ | $\text{B}$ | $5$ | | | $7$ | $2\times 10^5$ | $2\times 10^5$ | $10^9$ | $1$ | $\text{C}$ | $20$ | | | $8$ | $2\times 10^5$ | $2\times 10^5$ | $10^9$ | $1$ | | $10$ | $2,3,5,6,7$ | Special Property $\text{A}$: both $s_i$ and $t$ are `a`. Special Property $\text{B}$: $L=1$. Special Property $\text{C}$: $R=n$. For $100\%$ of the data: $1\le n,m,\lvert t\rvert\le 2\times 10^5$, $1\le q\le 2\times 10^5$, $1\le a_i\le 10^9$, $o\in\{0,1\}$, $0\le \text{sid}\le 8$, and $1\le L,R\le n$ or $L,R=-1$. Translated by ChatGPT 5