CF498D Traffic Jams in the Land

一、题目

点此看题

二、解法

由于 $a_i\le6$，并且 $lcm(1,2,3,4,5,6)=60$，这道题要求区间查询和单点修改，那么可以考虑建立一颗线段树，每个节点上的 $f[i]$，表示时间模 $60$的余 $i$的时候开始，走完这个节点代表的区间的消耗时间。

#include <cstdio>
#include <iostream>
using namespace std;
const int M = 100005;
int read()
{int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int n,m,a[M],f[4*M][62];
void up(int i)
{for(int j=0;j<60;j++)f[i][j]=f[i<<1][j]+f[i<<1|1][(j+f[i<<1][j])%60];
}
void build(int i,int l,int r)
{if(l==r){for(int j=0;j<60;j++)f[i][j]=1+(j%a[l]==0);return ;}int mid=(l+r)>>1;build(i<<1,l,mid);build(i<<1|1,mid+1,r);up(i);
}
void upd(int i,int l,int r,int id,int x)
{if(l==r){for(int j=0;j<60;j++)f[i][j]=1+(j%x==0);return ;}int mid=(l+r)>>1;if(id<=mid) upd(i<<1,l,mid,id,x);else upd(i<<1|1,mid+1,r,id,x);up(i);
}
int ask(int i,int l,int r,int L,int R,int x)
{if(L>r || l>R) return 0;if(L<=l && r<=R) return f[i][x];int mid=(l+r)>>1;int ls=ask(i<<1,l,mid,L,R,x);return ls+ask(i<<1|1,mid+1,r,L,R,(x+ls)%60);
}
signed main()
{n=read();for(int i=1;i<=n;i++)a[i]=read();build(1,1,n);m=read();for(int i=1;i<=m;i++){char c;cin>>c;if(c=='C'){int x=read(),d=read();upd(1,1,n,x,d);}else{int l=read(),r=read()-1;printf("%d\n",ask(1,1,n,l,r,0));}}
}