Doom HDU - 5239 （找规律+线段树）

时间：2021-03-09 11:43:33

 题目链接：

 题目大意：首先是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 ;

 }

、

相关文章