题面描述：

一些国家由（n + 1）个城市组成，位于一条直路上。我们用连续的整数从1到n + 1按照高速公路上出现的顺序对城市进行编号。因此，城市由高速公路的n段连接起来，第i段连接城市i和i + 1。高速公路的每一段都与一个正整数ai相关联 - 表示何时交通拥堵期出现在该段上。

为了从城市x到城市y（x <y），一些司机使用以下策略。

最初驾驶员在城市x，当前时间t等于0。在驾驶员抵达城市之前，他会采取以下行动：

1.如果当前时间t是ax的倍数，那么高速公路号x的段现在有交通问题，驾驶员在当前城市停留一个单位时间（当前t = t + 1）。

2.如果当前时间t不是ax的倍数，那么高速公路号x的段现在是畅通的，驾驶员使用一个单位时间移动到城市x + 1（当前t = t + 1且x = x + 1）。

你正在开发一个新的交通控制系统。您要连续处理两种类型的q查询：

A：我们应用上面描述的策略，确定从城市x到城市y（x <y）之后的时间t的最终值。请注意，对于每个查询t初始值为0。

C：用值y替换出现在段号x上的堵塞时段（令ax = y）。

Input

10 2 5 3 2 3 5 3 4 2 4 10 C 10 6 A 2 6 A 1 3 C 3 4 A 3 11 A 4 9 A 5 6 C 7 3 A 8 10 A 2 5

Output

5 3 14 6 2 4 4

这道题还是不是那么好想的……

我们需要发现一个性质：对于0s和60s来说，我们只要走相同的路得到的时间%60都是一样的。

（原因很简单，2-6最小公倍数为60）

所以我们开线段树tree[i][j]表示i区间从js（0<=j<60）开始从头走到尾的最终时间。

build的时候公式如下：

tree[a][i]=tree[a*2+1][tree[a*2][i]%tmax]+tree[a*2][i]/tmax*tmax;

gai的时候和build差不多。

询问的话……看代码吧。

（祝贺60棵线段树AC第一道CF题）

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;inline int read(){    int X=0,w=1; char ch=0;    while(ch<'0'||ch>'9') {
   if(ch=='-') w=-1;ch=getchar();}    while(ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();    return X*w;}const int tmax=60;int tree[400001][tmax];int b[100001];void build(int a,int l,int r){    if(l==r){   　　 for(int i=0;i
         
          >1;    build(a*2,l,mid);    build(a*2+1,mid+1,r);    for(int i=0;i
          
           r1||r
           
            >1; int k1=check(a*2,l,mid,l1,r1,t); int k2=check(a*2+1,mid+1,r,l1,r1,k1); return k2;}void gai(int a,int l,int r,int x,int y){ if(x
            
             
              >1; gai(a*2,l,mid,x,y); gai(a*2+1,mid+1,r,x,y); for(int i=0;i
              
               >c; 　　 int x=read(); 　　int y=read(); 　　 if(c=='A'){ 　　 printf("%d\n",check(1,1,n,x,y-1,0)); 　　 }else{ 　　 gai(1,1,n,x,y); 　　 } } return 0;}