题面：有n条公路一次连接着n + 1个城市，每一条公路有一个堵塞时刻a[i]，如果当前时间能被a[i]整除，那么通过这条公路需要2分钟；否则需要1分钟。
现给出n条公路的a[i]，以及m次操作。每一次操作：1.C x d：将第x条的堵塞时刻改为d。2.A x y：询问从城市x到城市y的所需时间。
这能想到是一个线段树的题，虽然做过好多道线段树的题，但遇到这种思路比较新奇的题，独立的想出来还是有一点困难。
于是稍微参照了一下题解。
我们观察一下a[i]，2 <= a[i] <= 6，很小，而且这些数的最小公倍数最大只有60，那么对于每一个节点，我们开一个tim[60]的数组，tim[j]维护在时刻 j ，通过这段区间需要的时间。
那么区间合并的时候就是 j 从0~59枚举，这个区间的第 j 个时刻花费的时间等于左区间的从 j 时刻花费的时间x，加上右区间从j + x时刻花费的时间。于是这题就完事啦。
时间复杂度O(mlogn * 60)。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 1e5 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n, m;
char s[]; struct Tree
{
int l, r;
int tim[];
}t[maxn << ];
void pushup(int now)
{
for(int i = ; i < ; ++i)
t[now].tim[i] = t[now << ].tim[i] + t[now << | ].tim[(i + t[now << ].tim[i]) % ];
}
void build(int L, int R, int now)
{
t[now].l = L; t[now].r = R;
if(L == R)
{
int x = read();
for(int i = ; i < ; ++i)
if(!(i % x)) t[now].tim[i] = ;
else t[now].tim[i] = ;
return;
}
int mid = (L + R) >> ;
build(L, mid, now << );
build(mid + , R, now << | );
pushup(now);
}
void update(int idx, int d, int now)
{
if(t[now].l == t[now].r)
{
for(int i = ; i < ; ++i)
if(!(i % d)) t[now].tim[i] = ;
else t[now].tim[i] = ;
return;
}
int mid = (t[now].l + t[now].r) >> ;
if(idx <= mid) update(idx, d, now << );
else update(idx, d, now << | );
pushup(now);
}
int query(int L, int R, int now, int Tim)
{
if(t[now].l == L && t[now].r == R) return t[now].tim[Tim % ];
int mid = (t[now].l + t[now].r) >> ;
if(R <= mid) return query(L, R, now << , Tim);
else if(L > mid) return query(L, R, now << | , Tim);
else
{
int ret = query(L, mid, now << , Tim);
ret += query(mid + , R, now << | , (Tim + ret) % );
return ret;
}
} int main()
{
n = read();
build(, n, );
m = read();
for(int i = ; i <= m; ++i)
{
scanf("%s", s);
if(s[] == 'C')
{
int x = read(), d = read();
update(x, d, );
}
else
{
int L = read(), R = read();
write(query(L, R - , , )); enter; //别忘 R - 1
}
}
return ;
}