题目大意
有一个长度为 n n n 的序列，支持以下两种操作：
- 将区间内的每个数分别平方
- 查询区间和对 998244353 取模的结果
n ≤ 2 × 1 0 5 n≤2\times 10^5 n≤2×105。
题解
赛时想破头了不会，最后决定写一个暴力，写暴力前先随便打了个表，结果发现每个数的循环节长度好像都不超过30，再仔细看看发现循环节长度的最大公倍数是24。
于是直接写一棵线段树，对于每个数存下他的一个周期，每次操作就是整体往右移一个位置。
然后我们就做完了。
至于循环节长度是24的因数的证明……我并不会，看了眼题解，大意好像是，平方相当于指数乘2，因此循环节长度的lcm为 2 x 2^x 2x 的循环节长度，具体跑一下发现是24。感性理解了一下，好似说得很有道理，但赛时想不到（）反正能过就行，打表yyds。
Code
#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
using namespace std;const int N=2e5+5,K=24,mod=998244353;int n,m,a[N];struct segment_tree{int h[N<<2][K+5],laz[N<<2],c[N<<2];void pushup(int p){c[p]=min(c[ls],c[rs]);for(int i=0;i<K;i++)h[p][i]=(h[ls][i]+h[rs][i])%mod;}void build(int p,int l,int r){if(l==r){h[p][0]=a[l]; for(int i=1;i<K;i++)h[p][i]=1ll*h[p][i-1]*h[p][i-1]%mod;return;}int mid=l+r>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(p);}void pushdown(int p){int t[K+5];laz[p]%=K;if(laz[p]==0) return;for(int i=0;i<K;i++)t[i]=h[ls][i];for(int i=0;i<K;i++)h[ls][i]=t[(i+laz[p])%K];for(int i=0;i<K;i++)t[i]=h[rs][i];for(int i=0;i<K;i++)h[rs][i]=t[(i+laz[p])%K];laz[ls]=(laz[ls]+laz[p])%K,laz[rs]=(laz[rs]+laz[p])%K;laz[p]=0;}void update(int p,int l,int r,int a,int b){if(a<=l&&b>=r&&c[p]>=K){int t[K+5];memcpy(t,h[p],sizeof(t));for(int i=0;i<K;i++)h[p][i]=t[(i+1)%K];laz[p]++;return;}if(l==r){c[p]++;h[p][0]=h[p][1];for(int i=1;i<K;i++)h[p][i]=1ll*h[p][i-1]*h[p][i-1]%mod;return;}if(laz[p]) pushdown(p);int mid=l+r>>1;if(a<=mid) update(ls,l,mid,a,b);if(b>mid) update(rs,mid+1,r,a,b);pushup(p);}int query(int p,int l,int r,int a,int b){if(a<=l&&b>=r) return h[p][0];if(laz[p]) pushdown(p);int mid=l+r>>1,res=0;if(a<=mid) res=(res+query(ls,l,mid,a,b))%mod;if(b>mid) res=(res+query(rs,mid+1,r,a,b))%mod;return res;}
}t;int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);t.build(1,1,n);for(int i=1,opt,x,y;i<=m;i++){scanf("%d%d%d",&opt,&x,&y);if(opt==1) t.update(1,1,n,x,y);else printf("%d\n",t.query(1,1,n,x,y));}return 0;
}
