[SHOI2010]滚动的正四面体

正四面体总共有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”，那么第1、4、6秒内A面是朝下的。此时，如果SECSA向你询问第3秒到第6秒的情况，你就应该回答“2”。而SECSA将第3条指令修改为“R”的话，指令串就变成了“LLRLB”，那么正四面体就只有在第1、5秒内A面朝下了。如图 5所示：一个正四面体的一次滚动显然有3个方向可以选择：向左（L）、向右（R）、向后（B）。如图 4所示：

输入文件的第一行是一个整数n，表示指令串中包含的指令条数。
输入文件的第二行是一个字符串，共包含n个字符，每个字符是“L”“R”“B”之一，表示初始的指令串。
输入文件的第三行是一个整数m，表示你的程序需要处理的操作总数。
接下去m行，每行描述一个操作，为以下两种格式之一：
(1)0 i c：表示把第i个操作改成c，c为“L”“R”“B”之一
(2)1 L R：表示询问第L秒到第R秒内，A面有多少秒朝下
输入文件保证：1<=i<=n，1<=L<=R<=n+1。

#include<bits/stdc++.h> using namespace std; const int N=2e5,inf=1<<16; int read(){ int s=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*f; } int ind[256]; int readc(){ int ch=getchar(); while(ch<'A'||ch>'Z') ch=getchar(); return ind[ch]; } int nx[N][4],c[N][4],ss[32],sp=0; int nx0[3][4]={{1,2,0,3},{1,3,2,0},{1,0,3,2}}; inline void sets(int w,int x){ for(int j=0;j<4;++j)c[w][j]=!(nx[w][j]=nx0[x][j]); } inline void up(int w){ int l=w<<1,r=l^1; for(int j=0;j<4;++j)nx[w][j]=nx[r][nx[l][j]],c[w][j]=c[l][j]+c[r][nx[l][j]]; } int main(){ ind['L']=0;ind['R']=1;ind['B']=2; int n=read(); for(int i=1,x,w;i<=n;++i){x=readc();sets(i+inf-1,x);} for(int i=inf-1;i;--i)up(i); for(int q=read();q;--q) if(read()){ int l=read()-2,r=read()-1,v=0,s=0; if(l>=0){ for(int w=l+inf;w;w>>=1)if(w&1)ss[sp++]=w^1; while(sp){ int w=ss[--sp]; s-=c[w][v]; v=nx[w][v]; } }else ++s; for(int w=r+inf;w;w>>=1)if(w&1)ss[sp++]=w^1; while(sp){ int w=ss[--sp]; s+=c[w][v]; v=nx[w][v]; } printf("%d\n",s); } else{ int w=read()+65535,x=readc(); sets(w,x); for(w>>=1;w;w>>=1)up(w); } return 0; }

详情