题解 CF498D Traffic Jams in the Land

线段树

首先观察数据范围，发现 $a_i \le6$ ，这个是一个非常有用的性质。

发现 $\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)$ 的 $push\_up$ 。

那么我们就可以以 $O(n \log n \times 60)$ 的优秀复杂度通过此题。

代码：

#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647
#define lc(a) ((a) << 1)
#define rc(a) ((a) << 1 | 1)

int inp(){
    char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    int sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum;
}

int a[100010];
struct SEG_Tree{
    struct SEG{
        int l;
        int r;
        int f[61];
    }t[400010];

    void push_up(int cur){
        for(int i = 0; i < 60; i++)
            t[cur].f[i] = t[rc(cur)].f[(i + t[lc(cur)].f[i]) % 60] + t[lc(cur)].f[i];
    }

    void build(int cur, int l, int r){
        t[cur].l = l;
        t[cur].r = r;
        if(l == r){
            for(int i = 59; i >= 0; i--)
                t[cur].f[i] = 1 + (i % a[l] == 0);
            return ;
        }
        int mid = (l + r) >> 1;
        build(lc(cur), l, mid);
        build(rc(cur), mid + 1, r);
        push_up(cur);
    }

    void modify(int cur, int x, int c){
        if(t[cur].l == t[cur].r){
            a[x] = c;
            for(int i = 59; i >= 0; i--)
                t[cur].f[i] = 1 + (i % a[x] == 0);
            return ;
        }
        if(x <= t[lc(cur)].r)
            modify(lc(cur), x, c);
        else
            modify(rc(cur), x, c);
        push_up(cur);
    }

    int query(int cur, int l, int r, int x){
        if(t[cur].l > r || t[cur].r < l)
            return 0;
        if(t[cur].l >= l && t[cur].r <= r){
            // printf("[%d, %d].f[%d] = %d\n", t[cur].l, t[cur].r, x, t[cur].f[x]);
            return t[cur].f[x];
        }
        int ls = query(lc(cur), l, r, x);
        return ls + query(rc(cur), l, r, (x + ls) % 60);
    }
}t;

int main(){
    int n = inp();
    for(int i = 1; i <= n; i++)
        a[i] = inp();
    t.build(1, 1, n);
    int m = inp();
    while(m--){
        char op = getchar();
        while(op != 'C' && op != 'A')
            op = getchar();
        if(op == 'C'){
            int x = inp();
            int c = inp();
            t.modify(1, x, c);
        } else {
            int l = inp();
            int r = inp() - 1;
            printf("%d\n", t.query(1, l, r, 0));
        }
    }
}

Dilute

题解 CF498D Traffic Jams in the Land

线段树