floyd判环+带暴力成分的线段树

题意：维护一种数组结构，支持区间内所有元素自幂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;
}