题目链接：
题目大意：首先是T组测试样例，然后n个数，m次询问，然后每一次询问给你一个区间，问你这个这段区间的加上上一次的和是多少，查询完之后，这段区间里面的每个数变为原来的平方。
具体思路：这个模数，和正常的模数不一样。
然后通过打表能发现，每个数不断自身平方对p取模后经过有限次 就不会变化了，
测试少于30次
所以也就是说每个节点至多会被更新30次。
注意会爆long long ，需要用unsigned long long .
AC代码：
#include<bits/stdc++.h>
using namespace std;
# define inf 0x3f3f3f3f
# define ull unsigned long long
# define lson l,mid,rt<<
# define rson mid+,r,rt<<|
const int maxn = 4e5+;
const ull mod = ;
struct node
{
ull sum;
int flag;
} tree[maxn];
ull qsmu(ull t1,ull t2)
{
ull ans=0ll;
while(t2)
{
if(t2&)
ans=(ans+t1)%mod;
t2>>=;
t1=(t1+t1)%mod;
}
return ans;
}
ull tot;
void up(int rt)
{
tree[rt].sum=(tree[rt<<].sum+tree[rt<<|].sum)%mod;
tree[rt].flag=(tree[rt<<].flag&tree[rt<<|].flag);
}
void build(int l,int r,int rt)
{
tree[rt].flag=;
tree[rt].sum=;
if(l==r)
{
scanf("%lld",&tree[rt].sum);
return ;
}
int mid=l+r>>;
build(lson);
build(rson);
up(rt);
}
void update(int l,int r,int rt,int L,int R)
{
if(R<l||r<L||tree[rt].flag)
return ;
if(l==r)
{
ull tmp=tree[rt].sum;
tree[rt].sum=qsmu(tree[rt].sum,tree[rt].sum);
if(tmp==tree[rt].sum)
tree[rt].flag=;
return ;
}
int mid=(l+r)>>;
update(lson,L,R);update(rson,L,R);
up(rt);
}
void ask(int l,int r,int rt,int L,int R)
{
if(R<l||r<L)
return ;
if(L<=l&&R>=r)
{
tot=(tot+tree[rt].sum)%mod;
return ;
}
int mid=(l+r)>>;
ask(lson,L,R);ask(rson,L,R);
up(rt);
}
int main()
{
int T;
int Case=;
scanf("%d",&T);
while(T--)
{
tot=;
int m,n;
scanf("%d %d",&n,&m);
build(,n,);
printf("Case #%d:\n",++Case);
while(m--)
{
int l,r;
scanf("%d %d",&l,&r);
ask(,n,,l,r);
printf("%lld\n",tot);
update(,n,,l,r);
}
}
return ;
}
、