题目大意:
给坐标轴1~n的点,每个点有一个权值,从一个点走到下一个点需要1s,如果当前时间是权值的倍数就要多花1s
给出q组操作,C表示单点修改权值,A表示询问0时刻x出发到y的时间
题解:因为权值只有2,3,4,5,6,所以60是一个周期,我们维护一颗线段树,维护0到59时刻出发从l到r+1用的时间
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 100010
using namespace std;
struct node
{
int l,r,tim[];
}t[*N];
int n,q,a[N],x,y;
char s[N];
void pushup(int p)
{
for (int i=;i<;i++)
t[p].tim[i]=t[*p].tim[i]+t[*p+].tim[(t[*p].tim[i]+i)%];
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if (l!=r)
{
int mid=l+r>>;
build(*p,l,mid);
build(*p+,mid+,r);
pushup(p);
}
else
for (int i=;i<;i++)
t[p].tim[i]=+!(i%a[l]);
}
void modify(int p,int l,int k)
{
int ll=t[p].l,rr=t[p].r,mid=ll+rr>>;
if (ll==l && ll==rr)
{
for (int i=;i<;i++)
t[p].tim[i]=+!(i%k);
return;
}
if (l<=mid) modify(*p,l,k);
else modify(*p+,l,k);
pushup(p);
}
int query(int p,int x,int y,int ti)
{
int ll=t[p].l,rr=t[p].r,mid=ll+rr>>;
if (x==ll && y==rr)
return t[p].tim[ti%];
if (y<=mid)
return query(*p,x,y,ti);
if (x>mid) return query(*p+,x,y,ti);
int tmp=query(*p,x,mid,ti);
return tmp+query(*p+,mid+,y,(ti+tmp)%);
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",a+i);
a[n+]=;
build(,,n+);
scanf("%d",&q);
while (q--)
{
scanf("%s",s);
scanf("%d%d",&x,&y);
if (s[]=='C')
modify(,x,y);
else
printf("%d\n",query(,x,y-,));
}
return ;
}