题解归档 - cf498D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf498D
• 本地来源：problems/cf498D/idea.md
• 题目链接：https://codeforces.com/contest/498/problem/D
• 原始标题：CF498D — Traffic Jams in the Land

思路

CF498D — Traffic Jams in the Land

题意

$n$ 段公路连接 $n+1$ 座城市。第 $i$ 段周期为 $a_i\in[2,6]$。从城市 $x$ 出发、时刻 $t=0$，每步：

• 若 $t$ 是 $a_x$ 的倍数，堵车，原地耗 1 时刻；
• 否则沿第 $x$ 段前进到 $x+1$，耗 1 时刻。

支持两类操作：查询从 $x$ 到 $y$ 的总时刻；把第 $x$ 段周期改为 $y$。

关键观察

单段通行增量 $d(t,a)=1+[t\bmod a=0]$，只可能是 1 或 2。

所有 $a_i\le 6$，判断 $t\bmod a_i$ 只需知道 $t\bmod 60$（$\mathrm{lcm}(2,3,4,5,6)=60$）。

做法

线段树每个结点存长度 60 的转移：

• nx[r]：从余数 $r$ 出发走完该区间后的余数；
• add[r]：对应增加的总时刻。

叶子（周期 $a$）：cost=1+(r%a==0)，add[r]=cost，nx[r]=(r+cost)%60。

合并左右儿子：先走左区间再走右区间，按 nx 串联 add。

查询 A x y：对段 $[x,y-1]$ 查询，初态余数 0；修改 C x y：单点重建叶子。

复杂度

建树/修改 $O(n\log n)$ 或单次修改 $O(\log n)$；查询 $O(\log n)$。$n,q\le 10^5$ 可过。

验证

样例通过；本地对拍 500 组（$n\le 30$，$q\le 40$）与 $O(n)$ 暴力一致。

代码

来源：problems/cf498D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:28:37
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e5+5,md=60;
ll n,q,i,j,k,x,y,zc,pd,cur,dq,cnt,ans;
ll a[maxn+5];
struct tnode{
    ll c[md],r[md];
};
tnode t[4*maxn+5];
tnode leaf(ll v){
    tnode res;
    for(i=0;i<md;i++){
        cur=i;
        zc=0;
        while(cur%v==0){
            zc++;
            cur=(cur+1)%md;
        }
        pd=i+zc+1;
        res.c[i]=pd/md;
        res.r[i]=pd%md;
    }
    return res;
}
tnode merge(tnode u,tnode v){
    tnode res;
    for(i=0;i<md;i++){
        res.c[i]=u.c[i]+v.c[u.r[i]];
        res.r[i]=v.r[u.r[i]];
    }
    return res;
}
void build(ll root,ll l,ll r){
    if(l==r){
        t[root]=leaf(a[l]);
        return;
    }
    ll mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    t[root]=merge(t[root*2],t[root*2+1]);
}
void upd(ll root,ll l,ll r,ll pos,ll v){
    if(l==r){
        a[pos]=v;
        t[root]=leaf(v);
        return;
    }
    ll mid=(l+r)/2;
    if(pos<=mid) upd(root*2,l,mid,pos,v);
    else upd(root*2+1,mid+1,r,pos,v);
    t[root]=merge(t[root*2],t[root*2+1]);
}
tnode qry(ll root,ll l,ll r,ll ql,ll qr){
    if(ql<=l and r<=qr) return t[root];
    ll mid=(l+r)/2;
    if(qr<=mid) return qry(root*2,l,mid,ql,qr);
    if(ql>mid) return qry(root*2+1,mid+1,r,ql,qr);
    return merge(qry(root*2,l,mid,ql,qr),qry(root*2+1,mid+1,r,ql,qr));
}
int main(){
    char op;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    cin>>q;
    while(q--){
        cin>>op>>x>>y;
        if(op=='C'){
            upd(1,1,n,x,y);
        }
        else{
            tnode res=qry(1,1,n,x,y-1);
            ans=res.c[0]*md+res.r[0];
            cout<<ans<<"\n";
        }
    }
    return 0;
}