题解:打表一下到99971你会发现循环节的最小公倍数为48，因为是区间修改那么用线段树，接着我们在更新的时候只需要把该区间的标记一下被更新加一，合并区间的时候要加 上子区间被更新的次数，最后我们查询的时候要增加一个d表示上面的区间被更新几次，最后的答案就是T[(x+lazy[rt])H][rt]即可
#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<cstdio> #include<cmath> #include<set> #include<map> #include<cstdlib> #include<ctime> #include<stack> using namespace std; #define mes(a) memset(a,0,sizeof(a)) #define rep(i,a,b) for(i = a; i <= b; i++) #define dec(i,a,b) for(i = b; i >= a; i--) #define fi first #define se second #define ls rt<<1 #define rs rt<<1|1 #define mid (L+R)/2 #define lson ls,L,mid #define rson rs,mid+1,R typedef double db; typedef long long int ll; typedef pair<int,int> pii; typedef unsigned long long ull; const int mx = 1e5+5; #define mod 99971 const int x_move[] = {1,-1,0,0,1,1,-1,-1}; const int y_move[] = {0,0,1,-1,1,-1,1,-1}; int lazy[mx<<2]; int T[48][mx<<2]; void built(int rt,int L,int R){ lazy[rt] = 0; if(L==R){ scanf("%d",&T[0][rt]); T[0][rt] %= mod; for(int i = 1; i < 48; i++) T[i][rt] = 1ll*T[i-1][rt]*T[i-1][rt]%mod*T[i-1][rt]%mod; return ; } built(lson); built(rson); for(int i = 0; i < 48; i++){ T[i][rt] = (T[i][ls]+T[i][rs])%mod; } } void update(int rt,int L,int R,int l,int r){ if(l<=L&&R<=r){ lazy[rt] = (lazy[rt]+1)%mod; return; } if(r<=mid) update(lson,l,r); else if(l>mid) update(rson,l,r); else { update(lson,l,mid); update(rson,mid+1,r); } for(int i = 0; i < 48; i++){ T[i][rt] = (T[(i+lazy[ls])H][ls]+T[(i+lazy[rs])H][rs])%mod; } } int query(int rt,int L,int R,int l,int r,int d){ d = (d+lazy[rt])H; if(l<=L&&R<=r) return T[d][rt]; if(r<=mid) return query(lson,l,r,d); else if(l>mid) return query(rson,l,r,d); else return (query(lson,l,mid,d)+query(rson,mid+1,r,d))%mod; } int main(){ int n,q; int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); built(1,1,n); while(q--){ int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op == 1) update(1,1,n,l,r); else printf("%d\n",query(1,1,n,l,r,0)); } } return 0; }