鄂州网站制作人才招聘,绵阳 网站开发,thinkphp做网站后台,在家跟狗做网站视频正题
luogu CF498D 题目大意
给n个1-6的数#xff0c;让你进行以下操作#xff1a;
修改其中一个数从第x个数走到第y个数#xff08;x≤yx\leq yx≤y#xff09;#xff0c;到达一个点时#xff0c;如果当前时间能被该数整除#xff0c;那么时间2#xff0c;否则1让你进行以下操作
修改其中一个数从第x个数走到第y个数x≤yx\leq yx≤y到达一个点时如果当前时间能被该数整除那么时间2否则1初始时间为0问走到y的时间 解题思路
因为每个数 ≤6\leq 6≤6所以可以求出1-6的lcm为60计算时只要知道时间对60取模的结果就可以知道是否会被整除
考虑使用线段树每个点维护当前区间开始时时间模60的结果会使用的时间即可
时间复杂度 O(60×nlogn)O(60\times n\ log\ n)O(60×n log n) code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100100
using namespace std;
int n,t,x,y,v[N];
char c[N];
struct node
{int a[65];
};
node merge(node a,node b)
{node c;for(int i0;i60;i)c.a[i]a.a[i]b.a[(ia.a[i])%60];return c;
}
struct Tree
{#define ls x*2#define rs x*21node s[N2];void push_up(int x){s[x]merge(s[ls],s[rs]);return;}void get(int x,int y){for(int i0;i60;i)s[x].a[i]1;for(int i0;i*y60;i)s[x].a[i*y]2;return;}void build(int x,int l,int r){if(lr){get(x,v[l]);return;}int midlr1;build(ls,l,mid);build(rs,mid1,r);push_up(x);return;}void change(int x,int l,int r,int y,int z){if(lr){get(x,z);return;}int midlr1;if(ymid)change(ls,l,mid,y,z);else change(rs,mid1,r,y,z);push_up(x);return;}node ask(int x,int L,int R,int l,int r){if(LlRr)return s[x];int midLR1;if(rmid)return ask(ls,L,mid,l,r);else if(lmid)return ask(rs,mid1,R,l,r);else return merge(ask(ls,L,mid,l,mid),ask(rs,mid1,R,mid1,r));}
}T;
int main()
{scanf(%d,n);for(int i1;in;i)scanf(%d,v[i]);T.build(1,1,n);scanf(%d,t);while(t--){scanf(%s%d%d,c,x,y);if(c[0]C)T.change(1,1,n,x,y);else printf(%d\n,T.ask(1,1,n,x,y-1).a[0]);}return 0;
}
