BZOJ 4105

THUSC中很有意思的一道题：

提示：
1.还记得上帝造题的七分钟么？其中一个思想：如果每个元素有两种状态，对其中的一种进行暴力重构处理，另一种想办法打标记！
2.本题的模数很特殊，如果把 $x \rightarrow x^2$ 连边，那么是会形成环的。然而本题的模数让所形成的环长度很小，而且所有环的 $LCM$ 不大于 $60$ 。并且不在环中的点离环的距离不超过 $11$ （以上数据摘自 $POPOQQQ$ 的博客）

详细题解代码后：

#include <bits/stdc++.h>using namespace std;
const int maxn = 110000;
int n , m , p;int book[maxn] , cnt , inCircle[maxn];void dfs(int x)
{if(inCircle[x]) return;if(book[x] == cnt){int now = x;while(true){inCircle[now] = 1;now = (now * now)%p;if(now == x) break;}return;}book[x] = cnt;dfs((x*x)%p);
}int a[maxn] , s[maxn*4] , f[maxn*4] , w[maxn*4];
vector<int> g[maxn*4];void build(int o , int l , int r)
{if(l == r){s[o] = a[l];if(inCircle[s[o]]) {int x = s[o];while(true){g[o].push_back(x);x = (x * x)%p;if(x == s[o]) break;}}}else {int mid = (l+r)/2 , ls = o*2 , rs = ls + 1;build(ls , l , mid);build(rs , mid+1 , r);s[o] = s[ls] + s[rs];int l1 = g[ls].size() , l2 = g[rs].size();if(l1 && l2){int l = l1*l2 / __gcd(l1 , l2);for(int i=0;i<l;i++) g[o].push_back(g[ls][i%l1] + g[rs][i%l2]);}}
}void giveTag(int o , int t = 1)
{(w[o] += t) %= g[o].size();(f[o] += t) %= g[o].size();s[o] = g[o][w[o]];
}void pushDown(int o)
{if(g[o].size() && f[o]){giveTag(o*2 , f[o]);giveTag(o*2+1 , f[o]);f[o] = 0;}
}void modify(int o , int l , int r , int L , int R)
{if(L <= l && r <= R && g[o].size()){giveTag(o);return;}if(l == r)  {s[o] = (s[o] * s[o]) % p;if(g[o].empty() && inCircle[s[o]]) {int x = s[o];while(true){g[o].push_back(x);x = (x * x)%p;if(x == s[o]) break;}}}else {pushDown(o);int mid = (l+r)/2 , ls = o*2 , rs = ls + 1;if(L <= mid) modify(ls , l , mid , L , R);if(R >  mid) modify(rs , mid+1 , r , L , R);s[o] = s[ls] + s[rs]; w[o] = 0;if(g[ls].size() && g[rs].size()){int l1 = g[ls].size() , l2 = g[rs].size() , l = l1*l2 / __gcd(l1 , l2);g[o].clear();for(int i=0;i<l;i++) g[o].push_back(g[ls][(i+w[ls])%l1] + g[rs][(i+w[rs])%l2]);}}
}int query(int o , int l , int r , int L , int R)
{if(L <= l && r <= R) return s[o];else {pushDown(o);int mid = (l+r)/2 , res = 0;if(L <= mid) res += query(o*2 , l , mid , L , R);if(R >  mid) res += query(o*2+1 , mid+1 , r , L , R);return res;}
}int main()
{#ifndef ONLINE_JUDGEfreopen("in","r",stdin);#endifcin>>n>>m>>p;for(cnt = 0;cnt<p;cnt++) if(!book[cnt]) dfs(cnt);for(int i=1;i<=n;i++) scanf("%d" , a+i);build(1 , 1 , n);while(m--){int x , y , z;scanf("%d%d%d" , &x , &y , &z);if(!x) modify(1 , 1, n , y , z);else printf("%d\n" , query(1 , 1 , n , y , z));}return 0;
}