题意:维护一种数组结构,支持区间内所有元素自幂mod,区间求和的操作。
同ZOJ 4009,地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4009
因为模数比较小,考虑自幂多次后会产生循环节。可以使用KMP算法和floyd判环(龟兔赛跑算法)辅助寻找循环节。
KMP可以求出循环长度。
floyd判环则更加强大,不但能求出循环圈的大小,并且能够区分循环部分与非循环的部分
本题使用floyd判环的模板帖进去会得到如下结论:
1、所有数字均会在多次自幂之后进入一个长度为6的循环节。
2、一开始有些数字一开始就在循环圈上,有些数字不在循环圈上。但是操作多次之后所有数字一定都会进入循环节,并且这个操作次数不多。
题解:
预处理将0到2017的数字分成两类,一类是在长度为6的循环节中的数字,另一类是不在循环节中的数字。
建一颗线段树,一开始暴力更新。一旦发现区间内所有的数字均进入长度为6的循环节时,就改为处理这6种循环的区间和。并且将修改操作从暴力修改改为懒标记下放。
时间复杂度O(6mlogn),空间复杂度O(n)
#include<bits/stdc++.h> using namespace std; bool check1(int x) { int t=x; x=(x*x)%2018; x=(x*x)%2018; x=(x*x)%2018; x=(x*x)%2018; x=(x*x)%2018; x=(x*x)%2018; return x==t; } bool circle[2018]; const int MAXN=50005; long long A[MAXN]; struct tnode { long long sum[6]; bool in_circle; int l,r,lazy; }; struct Segment_Tree { tnode t[4*MAXN]; void pushdown(int root) { if(t[root].lazy!=0) { long long temp[6]; for(int i=0;i<6;++i) { temp[i]=t[root].sum[(i+t[root].lazy)%6]; } for(int i=0;i<6;++i) { t[root].sum[i]=temp[i]; } if(t[root].l!=t[root].r) { int ch=root<<1; t[ch].lazy+=t[root].lazy; t[ch+1].lazy+=t[root].lazy; } t[root].lazy=0; } } void update (int root) { int ch=root<<1; pushdown(ch); pushdown(ch+1); if(t[ch].in_circle&&t[ch|1].in_circle)t[root].in_circle=true; if(t[root].in_circle) { for(int i=0;i<6;++i) { t[root].sum[i]=t[ch].sum[i]+t[ch|1].sum[i]; } } else { t[root].sum[0]=t[ch].sum[0]+t[ch|1].sum[0]; } } void buildt(int root,int l,int r) { t[root].l=l; t[root].r=r; t[root].lazy=0; t[root].in_circle=false; for(int i=0;i<6;++i) { t[root].sum[i]=0; } if(l!=r) { int mid=(l+r)>>1; int ch=root<<1; buildt(ch,l,mid); buildt(ch+1,mid+1,r); update(root); } else { t[root].sum[0]=A[l]; if(circle[A[l]]) { t[root].in_circle=true; for(int i=1;i<6;++i) { t[root].sum[i]=t[root].sum[i-1]*t[root].sum[i-1]%2018; } } } } void change(int root,int l,int r) { if(l==t[root].l&&r==t[root].r) { if(t[root].in_circle) { t[root].lazy++; } else { if(t[root].l==t[root].r) { t[root].sum[0]=t[root].sum[0]*t[root].sum[0]%2018; if(circle[t[root].sum[0]]) { t[root].in_circle=true; for(int i=1;i<6;++i) { t[root].sum[i]=t[root].sum[i-1]*t[root].sum[i-1]%2018; } } } else { int mid=(t[root].l+t[root].r)>>1; int ch=root<<1; change(ch,l,mid); change(ch|1,mid+1,r); update(root); } } return; } int mid=(t[root].l+t[root].r)>>1; int ch=root<<1; if(r<=mid)change(ch,l,r); else if(l>mid)change(ch|1,l,r); else {change(ch,l,mid);change(ch|1,mid+1,r);} update(root); } long long sum(int root,int l,int r) { pushdown(root); if(t[root].l==l&&t[root].r==r) { return t[root].sum[0]; } int mid=(t[root].l+t[root].r)>>1; int ch=root<<1; if(r<=mid)return sum(ch,l,r); else if(l>mid)return sum(ch|1,l,r); else return sum(ch,l,mid)+sum(ch|1,mid+1,r); } }; Segment_Tree ST; int T,n,x,y,m; char que[8]; int main() { for(int i=0;i<2018;++i) { circle[i]=check1(i); } scanf("%d",&T); for(int cas=1;cas<=T;++cas) { printf("Case #%d:\n",cas); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%lld",&A[i]); } ST.buildt(1,1,n); scanf("%d",&m); while(m--) { scanf("%s %d %d",que,&x,&y); if(*que=='Q') { printf("%lld\n",ST.sum(1,x,y)); } else { ST.change(1,x,y); } } } return 0; }
全部评论
(0) 回帖