滚动的正四面体
题目描述
正四面体总共有4个面，每个面都是一个正三角形。现在把它的一个面标记上字母A，如图 3中所示，A标记在底面上：
于是，这个正四面体的滚动过程就可以用一个只包含“L”“R”“B”的字符串来描述。初始时，正四面体的A面朝下，现在SECSA将给这个正四面体一串滚动指令——当然就是一个这样的字符串——让这个正四面体每秒滚动一下。也就是说，第1秒内正四面体A面朝下，第1秒末执行第一条指令，第2秒末执行第2条指令，依次类推，直至将整个指令串执行完毕。
你的任务就是当SECSA询问你的时候告诉他：这个正四面体在第L秒到第R秒内A面有多少秒朝着地面。当然，SECSA可能因为对这个正四面体的滚动路径不满意，他随时会修改他的某一条指令。因此你的程序应该能执行下面两个操作： <o:p></o:p>
(1) 接受SECSA修个第i条指令的信息 <o:p></o:p>
(2) 回答SECSA的“在第L秒到第R秒内A面有多少秒朝着地面”的询问 <o:p></o:p>
例如，假如原指令串为“LLLLB”，那么第1、4、6秒内A面是朝下的。此时，如果SECSA向你询问第3秒到第6秒的情况，你就应该回答“2”。而SECSA将第3条指令修改为“R”的话，指令串就变成了“LLRLB”，那么正四面体就只有在第1、5秒内A面朝下了。如图 5所示： <o:p></o:p>
一个正四面体的一次滚动显然有3个方向可以选择：向左（L）、向 <v:shapetype id="_x0000_t202" path="m,l,21600r21600,l21600,xe" o:spt="202" coordsize="21600,21600"> <v:stroke joinstyle="miter"></v:stroke> <v:path o:connecttype="rect" gradientshapeok="t"></v:path> </v:shapetype><v:shape id="_x0000_s1026" stroked="f" type="#_x0000_t202" style="margin-top: 61143.9pt; z-index: 1; left: 0px; margin-left: 134217.727pt; width: 1in; text-indent: 0px; position: absolute; height: 12pt; text-align: left; mso-position-horizontal-relative: text; mso-position-vertical-relative: text"> <v:textbox inset="0,0,0,0" style="mso-next-textbox: #_x0000_s1026; mso-fit-shape-to-text: t"> </v:textbox> </v:shape>
|
<o:p> </o:p> |
|
<o:p> </o:p> |
|
<o:p> </o:p> |
|
<o:p> </o:p> |
输入格式
输入文件的第一行是一个整数n，表示指令串中包含的指令条数。 <o:p></o:p>
输入文件的第二行是一个字符串，共包含n个字符，每个字符是“L”“R”“B”之一，表示初始的指令串。 <o:p></o:p>
输入文件的第三行是一个整数m，表示你的程序需要处理的操作总数。 <o:p></o:p>
接下去m行，每行描述一个操作，为以下两种格式之一： <o:p></o:p>
(1) 0 i c：表示把第i个操作改成c，c为“L”“R”“B”之一 <o:p></o:p>
(2) <st1:chmetcnv w:st="on" unitname="l" sourcevalue="1" hasspace="True" negative="False" numbertype="1" tcsc="0"> 1 L </st1:chmetcnv> R：表示询问第L秒到第R秒内，A面有多少秒朝下 <o:p></o:p>
输入文件保证：1<=i<=N,1<=L<=R<=N+1
输出格式
输出文件对于每一个询问操作依次输出你的程序给出的回答，每个回答为一个整数，占一行。 <o:p></o:p>
5 LLLLB 3 1 3 6 0 3 R 1 3 6
2 1
数据范围与约定
第1个样例就是问题描述中的例子
1<=N<=60000,1<=m<=150000