题意：给一个数列，有两个操作，①将区间所有的数变为原来的三次方 ②求区间和。
题解：打表发现，0~99971的数的循环节都是48的因子，因此，我们可以记录线段树上当前区间的48种变化值，延迟更新标记表示已经进行了几次循环，所以之后就是传统的区间更新，与区间询问。
AC代码：
#include<stdio.h>
#include<string.h>
#define mod 99971
typedef long long ll;
int a[100005];
int tree[100005*4][48],add[100005*4],mark[48];
void build(int L,int R,int root)
{
if(L==R)
{
tree[root][0]=a[L]%mod;
for(int i=1;i<48;i++)
tree[root][i]=1ll*tree[root][i-1]*tree[root][i-1]%mod*tree[root][i-1]%mod;
return ;
}
int mid=L+R>>1;
build(L,mid,root<<1);
build(mid+1,R,root<<1|1);
for(int i=0;i<48;i++)
tree[root][i]=(tree[root<<1][i]+tree[root<<1|1][i])%mod;
}
void pushdown(int root)
{
for(int i=0;i<48;i++)
mark[i]=tree[root<<1][i];
for(int i=0;i<48;i++)
tree[root<<1][i]=mark[(i+add[root])%48];
for(int i=0;i<48;i++)
mark[i]=tree[root<<1|1][i];
for(int i=0;i<48;i++)
tree[root<<1|1][i]=mark[(i+add[root])%48];
add[root<<1]+=add[root];
add[root<<1|1]+=add[root];
add[root]=0;
}
void update(int l,int r,int L,int R,int root)
{
if(l<=L&&R<=r)
{
add[root]++;
for(int i=0;i<48;i++)
mark[i]=tree[root][i];
for(int i=0;i<48;i++)
tree[root][i]=mark[(i+1)%48];
return ;
}
int mid=L+R>>1;
if(add[root])pushdown(root);
if(r<=mid)update(l,r,L,mid,root<<1);
else if(l>mid)update(l,r,mid+1,R,root<<1|1);
else
{
update(l,mid,L,mid,root<<1);
update(mid+1,r,mid+1,R,root<<1|1);
}
for(int i=0;i<48;i++)
tree[root][i]=(tree[root<<1][i]+tree[root<<1|1][i])%mod;
}
int query(int l,int r,int L,int R,int root)
{
if(l<=L&&R<=r)return tree[root][0];
int mid=L+R>>1;
if(add[root])pushdown(root);
if(r<=mid)return query(l,r,L,mid,root<<1);
else if(l>mid)return query(l,r,mid+1,R,root<<1|1);
else return (query(l,mid,L,mid,root<<1)+query(mid+1,r,mid+1,R,root<<1|1))%mod;
for(int i=0;i<48;i++)
tree[root][i]=(tree[root<<1][i]+tree[root<<1|1][i])%mod;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(tree,0,sizeof(tree));
memset(add,0,sizeof(add));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
while(m--)
{
int op,l,r;
scanf("%d%d%d",&op,&l,&r);
if(op==1)update(l,r,1,n,1);
else printf("%d\n",query(l,r,1,n,1));
}
}
}