P13242 「2.48sOI R1」你的名字


由于你不会交换身体，所以需要解决一道题目。 记 $\operatorname{occ}(u,v)$ 为**字符串 $\boldsymbol v$** 在**字符串 $\boldsymbol u$ 中**的出现次数。并记 $t[l,r]$ 表示字符串 $t$ 由第 $l$ 到第 $r$ 个字符组成的子串。 给定字符串序列 $(s_1,\dots,s_n)$ 和正整数序列 $(a_1,\dots,a_n)$ 以及字符串 $t$，有 $q$ 次询问，每次询问有四个参数 $l_1,r_1,l_2,r_2$，求： $$\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)$$ 对于 $o=1$ 的子任务，你需要支持在线询问。

共 $n+q+3$ 行。 - 第一行六个正整数 $\text{sid},n,q,o,L,R$。其中 $\text{sid}$ 表示测试点所在 Subtask 编号。特别地，对于样例，$\text{sid}=0$。其余量意义如题所示。 - 第 $2\sim n+1$ 行 $n$ 个字符串 $(s_1,\dots,s_n)$。 - 第 $n+2$ 行一个字符串 $t$。 - 第 $n+3$ 行 $n$ 个正整数 $(a_1,\dots,a_n)$。 - 第 $n+4\sim n+q+3$ 行每行四个正整数 $L_1,R_1,L_2,R_2$，描述一个询问。 对于第 $i$ 个询问，记第 $i-1$ 个询问的答案为 $\text{lst}$（若 $i=1$ 则 $\text{lst}=0$），则 $l_1,l_2,r_1,r_2$ 为： - $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$。 若 $l_1>r_1$，则交换 $l_1,r_1$。对于 $l_2,r_2$ 同理。 当 $L$ 不为 $-1$ 时，你需要将所有 $l_1$ 改为 $L$；当 $R$ 不为 $-1$ 时，你需要将所有 $r_1$ 改为 $R$（若初始的 $l_1>r_1$，本操作在交换 $l_1,r_1$ 之后进行）。

共 $q$ 行，第 $i$ 行表示第 $i$ 场梦境的⌈结⌋，即形式化题意中第 $i$ 个询问的答案。

**【样例解释 #1】** 以最后一组询问为例，$t[7,12] = \texttt{ababaa}$。给出要用的 $\text{occ}$ 数据： - $\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$。 答案为 $114\times 1+51\times 1+41\times 0 + 41\times 1 + 41\times 1 = 247$。 **【数据范围】** **本题采用捆绑测试。** 记 $m=\sum\limits_{i=1}^n\lvert s_i\rvert$。 | $\text{sid}=$ | $n,m,\lvert t\rvert\le$ | $q\le$ | $a_i\le$ | $o=$ |特殊性质| 分值 | 子任务依赖 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $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$ | 特殊性质 $\text{A}$：$s_i$ 与 $t$ 均为 `a`。 特殊性质 $\text{B}$：$L=1$。 特殊性质 $\text{C}$：$R=n$。 对于 $100\%$ 的数据，$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$，$1\le L,R\le n$ 或 $L,R=-1$。