上海大都會 H.A Simple Problem with Integers

---

題目描述

You have N integers A1, A2, ... , AN. You are asked to write a program to receive and execute two kinds of instructions:

1. C a b means performing Ai = (Ai2 mod 2018) for all Ai such that a ≤ i ≤ b.
2. Q a b means query the sum of Aa, Aa+1, ..., Ab. Note that the sum is not taken modulo 2018.

輸入描述:

The first line of the input is T(1≤ T ≤ 20), which stands for the number of test cases you need to solve.
The first line of each test case contains N (1 ≤ N ≤ 50000).The second line contains N numbers, the initial values of A1, A2, ..., An.? 0 ≤ Ai < 2018. The third line contains the number of operations Q (0 ≤ Q ≤ 50000). The following Q lines represents an operation having the format "C a b" or "Q a b", which has been described above. 1 ≤ a ≤ b ≤ N.

輸出描述:

For each test case, print a line "Case #t:" (without quotes, t means the index of the test case) at the beginning.
You need to answer all Q commands in order. One answer in a line.

分析

剛開始打表算錯了周期。。。又坑隊友了
每個元素平方最大周期為6，且6是其他所有周期的公倍數。我們可以在每個節點維護一個大小為6的數組，同時維護一個代表從數組中取哪個元素的指針。因為有的數在進入循環節前需要經過幾次修改，打表發現進入循環節前的修改次數都不超過5，所以可以在前五次暴力更新節點，之后才開始利用線段樹的lazy標記。

代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod=2018;
const int maxn=50050;
int cnt[maxn*4],sum[maxn*4][7],lazy[maxn*4],p[maxn*4];
void build(int l,int r,int id) {cnt[id]=p[id]=lazy[id]=0;if(l==r) {scanf("%d", &sum[id][0]);}else {int mid=(l+r)>>1;build(l,mid,id<<1);build(mid+1,r,id<<1|1);sum[id][0]=sum[id<<1][0]+sum[id<<1|1][0];}
}
void pushUp(int id) {cnt[id]=min(cnt[id<<1],cnt[id<<1|1]);if(cnt[id]>=5) {p[id]=0;for (int i = 0; i < 6; ++i)sum[id][i]=sum[id<<1][(p[id<<1]+i)%6]+sum[id<<1|1][(p[id<<1|1]+i)%6];}else sum[id][0]=sum[id<<1][p[id<<1]]+sum[id<<1|1][p[id<<1|1]];
}
void pushDown(int id) {p[id<<1]=(p[id<<1]+lazy[id])%6,lazy[id<<1]+=lazy[id];p[id<<1|1]=(p[id<<1|1]+lazy[id])%6,lazy[id<<1|1]+=lazy[id];lazy[id]=0;
}
void modify(int x,int y,int l,int r,int id) {if(l>r||l>y||r<x) return;if(l==r) {cnt[id]++;if(cnt[id]<5) {sum[id][0]=sum[id][0]*sum[id][0]%mod;}else if(cnt[id]==5) {p[id]=0;sum[id][0]=sum[id][0]*sum[id][0]%mod;for (int i = 1; i < 6; ++i){sum[id][i]=sum[id][i-1]*sum[id][i-1]%mod;}}else {p[id]=(p[id]+1)%6;}return;}if(lazy[id]) pushDown(id);if(x<=l&&y>=r) {int mid=(l+r)>>1;if(cnt[id]<5) {modify(x,y,l,mid,id<<1);modify(x,y,mid+1,r,id<<1|1);pushUp(id);}else {lazy[id]++;p[id]=(p[id]+1)%6;}return;}int mid=(l+r)>>1;if(x<=mid) modify(x,y,l,mid,id<<1);if(y>mid) modify(x,y,mid+1,r,id<<1|1);pushUp(id);
}
int query(int x,int y,int l,int r,int id) {if(l!=r && lazy[id]) pushDown(id);if(l>=x&&r<=y) {return sum[id][p[id]%6];}int mid=(l+r)>>1;int ans=0;if(x<=mid) ans+=query(x,y,l,mid,id<<1);if(y>mid) ans+=query(x,y,mid+1,r,id<<1|1);return ans;
}
int main(int argc, char const *argv[])
{int t,Case=0;scanf("%d", &t);while(t--){int n;scanf("%d", &n);build(1,n,1);int q;scanf("%d", &q);printf("Case #%d:\n", ++Case);while(q--){char str[3];int l,r;scanf("%s%d%d", str,&l,&r);if(str[0]=='Q') {printf("%d\n", query(l,r,1,n,1));}else {modify(l,r,1,n,1);}}}return 0;
}