UOJ Logo Universal Online Judge

UOJ

#577. 【ULR #1】打击复读

附件下载 统计

为了提升搜索引擎的关键词匹配度以加大访问量,某些网站可能在网页中无意义复读大量关键词。

你设计了一种方法量化评价一个文本(字符串 $s$)的“复读程度”:

字符串 $s$ 的下标从 $1\sim n$ 标号,第 $i$ 个字符被赋予两个权值:左权值 $wl_i$ 和右权值 $wr_i$ ,代表该位置的重要度。

定义一个子串 $s[l,r]$ 的左权值 $vl(s[l,r])$ 为:其在原串中各个匹配的左端点的左权值 $wl$ 和;右权值 $vr(s[l,r])$ 为:其在原串中各个匹配的右端点的右权值 $wr$ 和。这里 $t$ 在 $s$ 中所有的匹配是 $\forall 1 \le i \le j \le n,s[i,j]=t$,我们把这样的 $i$ 和 $j$ 分别叫做一个匹配的左右端点。

定义一个子串 $s[l,r]$ 的复读程度是它的左权值右权值的乘积,即 $w(s[l,r])=vl(s[l,r])\cdot vr(s[l,r])$ 。

$s$ 的“复读程度”定义为所有子串复读程度的和,即:

$$\sum\limits_{i=1}^{|S|}\sum\limits_{j=i}^{|S|}w(s[i,j]).$$

根据网站文本抽样的复读程度限流,就可以达到打击无意义复读行为的目的。

隔壁生命科学实验室正在分析跳蚤的基因序列。他们对基因的复读情况很感兴趣,于是顺便把这个锅丢给了你。

基因片段可以被视作字符集为 $\{A,T,G,C\}$ 的字符串,你要求出给定的基因片段 $S$ 的复读程度。

有些时候,由于新的科学发现,某个位置 $u$ 的左权值 $wl_u$ 会相应修改为 $v$,修改过后你需要给出基因片段 $S$ 的新的复读程度。

由于答案很大,你只需要输出答案对 $2^{64}$ 取模后的结果。

输入格式

第一行一个正整数 $n$ 表示基因片段长度,一个整数 $m$ 表示操作次数。

第二行一个字符串 $S$ 表示基因片段。

第三行 $n$ 个整数 $wl_i$ 表示左权值。

第四行 $n$ 个整数 $wr_i$ 表示右权值。

接下来 $m$ 行,每行给出两个整数 $u_i,v_i$ ,表示将位置 $u_i$ 的左权值 $wl_{u_i}$ 修改为 $v_i$ 。

输出格式

第一行输出一个整数,表示初始时 $S$ 的复读程度对 $2^{64}$ 取模后的结果。

接下来 $m$ 行,第 $i$ 行输出第 $i$ 次操作后 $S$ 的复读程度对 $2^{64}$ 取模后的结果。

样例一

input

5 0
ATATA
1 2 3 4 5
1 2 3 4 5

output

550

样例二

input

10 5
ACGTAGCGAG
3 2 7 8 0 8 0 1 9 9
8 1 1 9 8 9 8 8 8 9
2 2
3 6
10 9
10 2
5 3

output

5427
5427
5260
5260
4504
4927

限制与约定

对于所有数据,满足 $1\leq n,m\leq 5\times 10^5,0\leq wl_i,wr_i,v_i< 2^{64},1\leq u_i\leq n$。

子任务编号 $n\leq$ $wl_i,wr_i\leq$ $m\leq$ 特殊性质 分值
1 $100$ $10^5$ $100$ $10$
2 $10^5$ $0$ 数据随机生成 $20$
3 $30$
4 $1.5\times 10^5$ $2^{64}-1$ $5\times 10^5$ $20$
5 $5\times 10^5$ $20$

时间限制:$4\texttt{s}$

空间限制:$1\texttt{GB}$

注意常数因子带来的程序效率上的影响。

下载

样例数据下载