hdu 4578 Transformation

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     else
105     {
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
",search1(1,x,y,c)%10007);
135             }
136         }
137     }
138     return 0;
139 }
View Code