首页 > 代码库 > hdu 4578 Transformation

hdu 4578 Transformation

2024-07-17 13:07:54   217人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4578

题意：1,a,b,c代表在a,b区间的每一个数加上c；2,a,b,c代表在a,b区间的每一个数乘上c； 3,a,b,c代表在a,b区间的每一个数变为c；4,a,b,c是求在a,b区间的每一个数的c次方的和。

先乘后加。

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #define maxn 100010  5 using namespace std;  6   7 int n,m;  8 struct node  9 { 10     int r,l; 11     int sum; 12     int add; 13     int mul; 14     int sum2; 15     int sum3; 16 }tree[maxn*6]; 17  18 void build(int i,int l,int r) 19 { 20     tree[i].l=l; 21     tree[i].r=r; 22     tree[i].sum=0; 23     tree[i].add=0; 24     tree[i].mul=1; 25     tree[i].sum2=0; 26     tree[i].sum3=0; 27     if(l==r) return ; 28     int mid=(l+r)>>1; 29     build(i<<1,l,mid); 30     build(i<<1|1,mid+1,r); 31 } 32  33 void mull(int i,int data1,int data) 34 { 35     (tree[i].sum*=data1)%=10007; 36     tree[i].sum2=tree[i].sum2*data1%10007*data1%10007; 37     tree[i].sum3=tree[i].sum3*data1%10007*data1%10007*data1%10007; 38     (tree[i].mul*=data1)%=10007; 39     (tree[i].add*=data1)%=10007; 40     (tree[i].sum3+=((tree[i].r-tree[i].l+1)%10007*(data%10007*data%10007*data%10007)))%=10007; 41     (tree[i].sum3+=3*data%10007*tree[i].sum2%10007)%=10007; 42     (tree[i].sum3+=(3*data%10007*data%10007*tree[i].sum%10007))%=10007; 43     (tree[i].sum2+=(tree[i].r-tree[i].l+1)*(data*data%10007)%10007)%=10007; 44     (tree[i].sum2+=(2*data%10007*tree[i].sum%10007))%=10007; 45     (tree[i].sum+=(tree[i].r-tree[i].l+1)%10007*data%10007)%=10007; 46     (tree[i].add+=data)%=10007; 47 } 48 void down(int i) 49 { 50     if(tree[i].l==tree[i].r) return ; 51     mull(i<<1,tree[i].mul,tree[i].add); 52     mull(i<<1|1,tree[i].mul,tree[i].add); 53     tree[i].add=0; 54     tree[i].mul=1; 55 } 56 void update(int i,int l,int r,int data1,int data) 57 { 58     if(tree[i].l==l&&tree[i].r==r) 59     { 60         mull(i,data1,data); 61         return ; 62     } 63     down(i); 64     int mid=(tree[i].l+tree[i].r)>>1; 65     if(r<=mid) 66     { 67         update(i<<1,l,r,data1,data); 68     } 69     else if(l>mid) 70     { 71         update(i<<1|1,l,r,data1,data); 72     } 73     else 74     { 75         update(i<<1,l,mid,data1,data); 76         update(i<<1|1,mid+1,r,data1,data); 77     } 78     tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%10007; 79     tree[i].sum2=(tree[i<<1].sum2+tree[i<<1|1].sum2)%10007; 80     tree[i].sum3=(tree[i<<1].sum3+tree[i<<1|1].sum3)%10007; 81 } 82  83 int search1(int i,int l,int r,int ch) 84 { 85     if(tree[i].l==l&&tree[i].r==r) 86     { 87         if(ch==1) 88             return tree[i].sum; 89         else if(ch==2) 90             return tree[i].sum2; 91         else if(ch==3) 92             return tree[i].sum3; 93     } 94     down(i); 95     int mid=(tree[i].l+tree[i].r)>>1; 96     if(r<=mid) 97     { 98         return search1(i<<1,l,r,ch); 99     }100     else  if(l>mid)101     {102         return search1(i<<1|1,l,r,ch);103     }104     else105     {106         return (search1(i<<1,l,mid,ch)+search1(i<<1|1,mid+1,r,ch))%10007;107     }108 }109 110 int main()111 {112     while(scanf("%d%d",&n,&m)!=EOF)113     {114         if(n==0&&m==0) break;115         build(1,1,n);116         for(int i=1; i<=m; i++)117         {118             int x,y,op,c;119             scanf("%d%d%d%d",&op,&x,&y,&c);120             if(op==1)121             {122                 update(1,x,y,1,c);123             }124             else if(op==2)125             {126                 update(1,x,y,c,0);127             }128             else if(op==3)129             {130                 update(1,x,y,0,c);131             }132             else if(op==4)133             {134                 printf("%d\n",search1(1,x,y,c)%10007);135             }136         }137     }138     return 0;139 }
View Code

 


联系
我们