buaa2014校赛 1088 再也不会依赖任何人了----线段树
Description "任何人都不相信未来,任何人也都无法接受未来。 现在有一个数字序列,要对这个序列进行实时修改与询问。 但是询问的结果会非常非常大,所以只需要这个数对61取模的结果即可。 Input 输入文件包含多组数据,以EOF为结尾。 1≤n≤100,000,1≤m≤100,000,0≤序列内元素<230,1≤L≤R≤n 。 Output对于每个询问输出一行表示对应的结果。 Sample Input5 3 1 2 3 4 5 Q 1 5 S 1 5 Q 1 5 Sample Output42 36 Hint 对于第一个询问,结果为225,输出42 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("%dn",ans); } } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |