\(CF498D Traffic Jams In the Land\)
\(Soltuion:\) 发现 \(\mathrm{lcm}(1, 2, 3, 4, 5, 6)=60\)，把 \(t\) 在\(\mod 60\) 意义下进行不会影响结果的正确性。接下来继续考虑线段树，对于每个区间 \([l, r]\)，再对于每个可能的时间\(\mod 60\) 意义下的结果，我们维护如果在达到 \(l\) 的时候 \(t\mod 60 = i\)，那么达到 \(r + 1\) 需要花费多少时间。\(O(60)\) 的 \(pushup\)。\(O(n {\log} n×60)\)。
点击查看代码
const int N = 1e5 + 10;
#define ls u << 1
#define rs u << 1 | 1
struct node{ int l, r, f[61]; }tr[N << 2];
int n, m, a[N];
inline void pushup(int u){
for(int i = 0; i <= 59; i ++) tr[u].f[i] = tr[rs].f[(i + tr[ls].f[i]) % 60] + tr[ls].f[i];
}
inline void build(int u, int l, int r){
tr[u].l = l, tr[u].r = r;
if(l == r){ for(int i = 59; i >= 0; i --){ tr[u].f[i] = 1 + (i % a[l] == 0); } return; }
int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); pushup(u);
}
inline void modify(int u, int x, int c){
if(tr[u].l == tr[u].r){ a[x] = c; for(int i = 59; i >= 0; i --) tr[u].f[i] = 1 + (i % a[x] == 0); return; }
if(x <= tr[ls].r) modify(ls, x, c); else modify(rs, x, c); pushup(u);
}
inline int query(int u, int l, int r, int x){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l >= l && tr[u].r <= r){ return tr[u].f[x]; }
int L = query(ls, l, r, x); return L + query(rs, l, r, (x + L) % 60);
}
signed main(){
read(n); for(int i = 1; i <= n; i ++){ read(a[i]); } build(1, 1, n);
read(m); while(m --){
char op; cin >> op; if(op == 'C'){
int x, c; read(x), read(c); modify(1, x, c);
}else{
int l, r; read(l), read(r); r --; print(query(1, l, r, 0)), puts("");
}
}
}