HDU4578Transformation线段树的加、乘、变、次方操作

Sample Input

Sample Output

307
7489

题意：
给出n，m，表示该数有n个节点，m次操作。
接下来m次操作，op、x、y、z，
op=1时，将区间内每个元素+z
op=2时，将区间内每个元素*z
op=3时，将区间内每个元素都变成z
op=4时，求出区间内每个元素的p次方之和输出且对mod10007取余。


数组说明：

a[i]:该区间相等元素值
book[i]: 假设该节点下面的儿子节点全部相等则标记为0，否则为1


对于op=4时的次方操作：

if(L<=l&&r<=R&&book[i]==0)
{
    ll ans=1;
    for(int k=0; k<p; k++)
        ans=(ans*a[i])%mod;
    ans=(ans*(r-l+1))%mod;
    return ans;
}

  1 #include<stdio.h>
  2 #include<map>
  3 #include<iostream>
  4 #include<string.h>
  5 #include<algorithm>
  6 #include<stack>
  7 #include<cmath>
  8 #include<vector>
  9 using namespace std;
 10 typedef long long ll;
 11 const int mod=10007;
 12 const int N=1e5+20;
 13 
 14 int a[4*N];
 15 bool book[4*N];
 16 
 17 void pushdown(int i)
 18 {
 19     if(book[i<<1]||book[i<<1|1])
 20         book[i]=1;
 21     else if(a[i<<1]!=a[i<<1|1])
 22         book[i]=1;
 23     else
 24     {
 25         book[i]=0;
 26         a[i]=a[i<<1]=a[i<<1|1];//因为a[i<<1]==a[i<<1|1]
 27     }
 28 }
 29 //1 x y 1 n
 30 void update(int i,int L,int R,int l,int r,int z,int op)
 31 {
 32     if(L<=l&&r<=R&&book[i]==0)//1不相等 0相等
 33     {
 34         if(op==1)
 35             a[i]=(a[i]+z)%mod;
 36         else if(op==2)
 37             a[i]=(a[i]*z)%mod;
 38         else if(op==3)
 39             a[i]=z;
 40         return;
 41     }
 42     if(book[i]==0)
 43     {
 44         book[i<<1]=book[i<<1|1]=0;
 45         a[i<<1]=a[i<<1|1]=a[i];
 46         book[i]=1;
 47     }
 48     int mid=(l+r)>>1;
 49     if(L<=mid)
 50         update(i<<1,L,R,l,mid,z,op);
 51     if(R>mid)
 52         update(i<<1|1,L,R,mid+1,r,z,op);
 53     pushdown(i);//a[i]=a[i<<1]+a[i<<1|1];
 54 }
 55 
 56 ll query(int i,int L,int R,int l,int r,int p)
 57 {
 58     if(L<=l&&r<=R&&book[i]==0)
 59     {
 60         ll ans=1;
 61         for(int k=0;k<p;k++)
 62             ans=(ans*a[i])%mod;
 63         ans=(ans*(r-l+1))%mod;
 64         return ans;
 65     }
 66     if(book[i]==0)
 67     {
 68         book[i<<1]=book[i<<1|1]=0;
 69         a[i<<1]=a[i<<1|1]=a[i];
 70         book[i]=1;
 71     }
 72     int mid=(l+r)>>1;
 73     ll ans=0;
 74     if(L<=mid)
 75         ans+=query(i<<1,L,R,l,mid,p);
 76     if(R>mid)
 77         ans+=query(i<<1|1,L,R,mid+1,r,p);
 78     return ans%mod;
 79 
 80 }
 81 
 82 int main()
 83 {
 84     int n,m,op,L,R,z;
 85     while(cin>>n>>m)
 86     {
 87         if(n==0&&m==0)
 88             break;
 89         memset(book,0,sizeof(book));//假设全相等标记为0//book[1]表示该节点下面的元素不相等
 90         memset(a,0,sizeof(a));//该区间相等元素值
 91         for(int i=0; i<m; i++)
 92         {
 93             cin>>op>>L>>R>>z;
 94             if(op!=4) //1+,2*,3变为z,
 95                 update(1,L,R,1,n,z,op);
 96             else //*z次方
 97             {
 98                 ll ans=query(1,L,R,1,n,z)%mod;
 99                 printf("%lld\n",ans);
100             }
101         }
102     }
103     return 0;
104 }