buaa2014校赛 1088 再也不会依赖任何人了----线段树

Description

"任何人都不相信未来，任何人也都无法接受未来。
既然这样，那么我再也不会依赖任何人了，也没必要让任何人理解。"
"所有的魔女，都由我一人来解决！" homura默言。

现在有一个数字序列，要对这个序列进行实时修改与询问。
·修改是把一段区间内所有数字都平方。
·询问是询问一段区间内数字和的平方。

但是询问的结果会非常非常大，所以只需要这个数对61取模的结果即可。

Input

输入文件包含多组数据，以EOF为结尾。
对于每组数据第一行有两个正整数n和m，n代表序列的元素数目，m代表操作/询问个数。
接下来一行有n个非负整数，表示原序列。
接下来有m行，每行由以下两种情况构成。
·S L R 表示把[L,R]这段区间内所有数字都平方一下，
·Q L R 表示询问[L,R]这段区间的和的平方。

1≤n≤100,000，1≤m≤100,000，0≤序列内元素<2³⁰，1≤L≤R≤n 。

Output

对于每个询问输出一行表示对应的结果。

Sample Input

Sample Output

42
36

Hint

对于第一个询问，结果为225，输出42
对于第二个询问，结果为3025，输出36

Author: Zhao XuanAng

a^60 = 1 (mod 61)

a^64 = a^4 (mod 61)

因此产生循环节

lazy表示，区间做了几次数的平方的操作

a^64,(6次操作) == a^4 (2次操作)

然后线段树。。

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f
 
int trans[6]={1,2,3,4,5,2};
int tran[4][6]=
{
    {2,3},{3,4},{4,5},{5,2}
};
struct node
{
    int l,r,lazy;
    int s[6];
    int mid()
    {
        return (l+r)>>1;
    }
}tree[4*100010];
int p[100010];
 
int tmp[6];
void process(int id,int t)
{
    if(t==0) return ;
    if(t==1)
    {
        for(int i=0;i<6;i++)
            tmp[i]=tree[id].s[trans[i]];
    }
    else
    {
        t=(t-2)%4;
        for(int i=0;i<6;i++)
            tmp[i]=tree[id].s[tran[t][i]];
    }
    for(int i=0;i<6;i++)
        tree[id].s[i]=tmp[i];
}
void pushup(int id)
{
    for(int i=0;i<6;i++)
        tree[id].s[i]=(tree[id<<1].s[i]+tree[id<<1|1].s[i])%61;
}
void pushdown(int id)
{
    if(tree[id].lazy)
    {
        tree[id<<1].lazy+=tree[id].lazy;
        tree[id<<1|1].lazy+=tree[id].lazy;
        process(id<<1,tree[id].lazy);
        process(id<<1|1,tree[id].lazy);
        tree[id].lazy=0;
    }
}
void build(int id,int x,int y)
{
    tree[id].l=x;
    tree[id].r=y;
    tree[id].lazy=0;
    if(x==y)
    {
        int val=p[x];
        for(int i=0;i<6;i++)
        {
            tree[id].s[i]=val;
            val=val*val%61;
        }
        return ;
    }
    int mid=tree[id].mid();
    build(id<<1,x,mid);
    build(id<<1|1,mid+1,y);
    pushup(id);
}
void change(int id,int y)
{
    if(tree[id].l==x && tree[id].r==y)
    {
        tree[id].lazy++;
        process(id,1);
        return ;
    }
    pushdown(id);
    int mid=tree[id].mid();
    if(y<=mid)
        change(id<<1,y);
    else if(x>=mid+1)
        change(id<<1|1,y);
    else
    {
        change(id<<1,mid);
        change(id<<1|1,y);
    }
    pushup(id);
}
int query(int id,int y)
{
    if(tree[id].l==x && tree[id].r==y)
    {
        return tree[id].s[0];
    }
    pushdown(id);
    int mid=tree[id].mid();
    if(y<=mid)
        return query(id<<1,y);
    else if(x>=mid+1)
        return query(id<<1|1,y);
    else
        return (query(id<<1,mid)+query(id<<1|1,y))%61;
}
int main()
{
    int n,m,i,j,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
            p[i]%=61;
        }
        build(1,1,n);
        char ch[4];
        while(m--)
        {
            scanf("%s",ch);
            int a,b;
            scanf("%d%d",&a,&b);
            if(ch[0]=='S')
            {
                change(1,a,b);
            }
            else
            {
                int ans=query(1,b);
                ans=ans*ans%61;
                printf("%d\n",ans);
            }
        }
    }
}