UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2518. [Shoi2010]滚动的正四面体

Statistics 下载数据

Description

正四面体总共有4个面,每个面都是一个正三角形。现在把它的一个面标记上字母A,如3中所示,A标记在底面上:

于是,这个正四面体的滚动过程就可以用一个只包含“L”“R”“B”的字符串来描述。初始时,正四面体的A面朝下,现在SECSA将给这个正四面体一串滚动指令——当然就是一个这样的字符串——让这个正四面体每秒滚动一下。也就是说,第1秒内正四面体A面朝下,第1秒末执行第一条指令,第2秒末执行第2条指令,依次类推,直至将整个指令串执行完毕。

你的任务就是当SECSA询问你的时候告诉他:这个正四面体在第L秒到第R秒内A面有多少秒朝着地面。当然,SECSA可能因为对这个正四面体的滚动路径不满意,他随时会修改他的某一条指令。因此你的程序应该能执行下面两个操作:

(1)                接受SECSA修个第i条指令的信息

(2)                回答SECSA的“在第L秒到第R秒内A面有多少秒朝着地面”的询问

例如,假如原指令串为“LLLLB”,那么第146秒内A面是朝下的。此时,如果SECSA向你询问第3秒到第6秒的情况,你就应该回答“2”。而SECSA将第3条指令修改为“R”的话,指令串就变成了“LLRLB”,那么正四面体就只有在第15秒内A面朝下了。如5所示:

一个正四面体的一次滚动显然有3个方向可以选择:向左(L)、向

 

 

 

 

右(R)、向后(B)。如4所示:

Input

输入文件的第一行是一个整数n,表示指令串中包含的指令条数。

输入文件的第二行是一个字符串,共包含n个字符,每个字符是“L”“R”“B”之一,表示初始的指令串。

输入文件的第三行是一个整数m,表示你的程序需要处理的操作总数。

接下去m行,每行描述一个操作,为以下两种格式之一:

(1)                0 i c:表示把第i个操作改成cc为“L”“R”“B”之一

(2)                1 L R:表示询问第L秒到第R秒内,A面有多少秒朝下

输入文件保证:1<=i<=N,1<=L<=R<=N+1

Output

输出文件对于每一个询问操作依次输出你的程序给出的回答,每个回答为一个整数,占一行。

Sample Input

5
LLLLB
3
1 3 6
0 3 R
1 3 6

Sample Output

2
1

Hint

1个样例就是问题描述中的例子





1<=N<=60000,1<=m<=150000

Source

Day1