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≤序列内元素<230，1≤L≤R≤n 。
Output
对于每个询问输出一行表示对应的结果。
Sample Input
5 3 1 2 3 4 5 Q 1 5 S 1 5 Q 1 5
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); } } } }
