Problem Description
Yuanfang is puzzled with the question below: There are n integers, a 1, a 2, …, a n. The initial values of them are 0. There are four kinds of operations. Operation 1: Add c to each number between a x and a y inclusive. In other words, do transformation a k<---a k+c, k = x,x+1,…,y. Operation 2: Multiply c to each number between a x and a y inclusive. In other words, do transformation a k<---a k×c, k = x,x+1,…,y. Operation 3: Change the numbers between a x and a y to c, inclusive. In other words, do transformation a k<---c, k = x,x+1,…,y. Operation 4: Get the sum of p power among the numbers between a x and a y inclusive. In other words, get the result of a x p+a x+1 p+…+a y p. Yuanfang has no idea of how to do it. So he wants to ask you to help him.
--by HDUoj
http://acm.hdu.edu.cn/showproblem.php?pid=4578
因为p<4,所以，直接线段树维护区间和，平方和，立方和，三棵树，打上乘法，加法，更改标记，注意down的顺序；
所以，会线段树的话，这题主要考代码能力......和信仰。
记得及时取模。
代码如下：
1 #include2 #define mod 10007 3 using namespace std; 4 5 long long tree[4][400000]; 6 long long mark1[400000],mark2[400000],mark3[400000]; 7 8 int n,m,L,R; 9 long long a,b; 10 11 void work(); 12 void build(int ,int ,int ); 13 void up(int ); 14 void down(int ,int ,int ); 15 void change(int ,int ,int ); 16 long long sum(int ,int ,int ); 17 18 int main() 19 { 20 while(1) 21 { 22 scanf("%d%d",&n,&m); 23 if(n==0&&m==0) 24 return 0; 25 work(); 26 } 27 } 28 29 void work() 30 { 31 int i; 32 long long ans=0; 33 build(1,n,1); 34 for(i=1;i<=m;i++) 35 { 36 scanf("%d%d%d%d",&b,&L,&R,&a); 37 if(b==4) 38 { 39 ans=sum(1,n,1); 40 printf("%lld\n",ans%mod); 41 } 42 else 43 change(1,n,1); 44 } 45 } 46 47 void build(int l,int r,int nu) 48 { 49 tree[1][nu]=tree[2][nu]=tree[3][nu]=mark1[nu]=mark3[nu]=0; 50 mark2[nu]=1; 51 if(l==r) 52 return ; 53 int mid=(l+r)>>1; 54 build(l,mid,nu<<1); 55 build(mid+1,r,nu<<1|1); 56 } 57 58 void up(int nu) 59 { 60 tree[1][nu]=(tree[1][nu<<1]+tree[1][nu<<1|1])%mod; 61 tree[2][nu]=(tree[2][nu<<1]+tree[2][nu<<1|1])%mod; 62 tree[3][nu]=(tree[3][nu<<1]+tree[3][nu<<1|1])%mod; 63 } 64 65 void down(int l,int r,int nu) 66 { 67 int mid=(l+r)>>1; 68 if(mark3[nu]) 69 { 70 tree[1][nu<<1]=tree[2][nu<<1]=tree[3][nu<<1]=0; 71 mark1[nu<<1]=0;mark2[nu<<1]=1; 72 mark3[nu<<1]=mark3[nu]; 73 tree[1][nu<<1|1]=tree[2][nu<<1|1]=tree[3][nu<<1|1]=0; 74 mark1[nu<<1|1]=0;mark2[nu<<1|1]=1; 75 mark3[nu<<1|1]=mark3[nu]; 76 } 77 tree[3][nu<<1]=(tree[3][nu<<1]*mark2[nu]*mark2[nu]*mark2[nu])%mod; 78 tree[2][nu<<1]=(tree[2][nu<<1]*mark2[nu]*mark2[nu])%mod; 79 tree[1][nu<<1]=(tree[1][nu<<1]*mark2[nu])%mod; 80 tree[3][nu<<1]=(tree[3][nu<<1]+3*tree[2][nu<<1]*mark1[nu]+3*tree[1][nu<<1]*mark1[nu]*mark1[nu]+(mid-l+1)*mark1[nu]*mark1[nu]*mark1[nu])%mod; 81 tree[2][nu<<1]=(tree[2][nu<<1]+2*mark1[nu]*tree[1][nu<<1]+(mid-l+1)*mark1[nu]*mark1[nu])%mod; 82 tree[1][nu<<1]=(tree[1][nu<<1]+mark1[nu]*(mid-l+1))%mod; 83 mark2[nu<<1]=(mark2[nu<<1]*mark2[nu])%mod; 84 mark1[nu<<1]=(mark1[nu<<1]*mark2[nu]+mark1[nu])%mod; 85 tree[3][nu<<1|1]=(tree[3][nu<<1|1]*mark2[nu]*mark2[nu]*mark2[nu])%mod; 86 tree[2][nu<<1|1]=(tree[2][nu<<1|1]*mark2[nu]*mark2[nu])%mod; 87 tree[1][nu<<1|1]=(tree[1][nu<<1|1]*mark2[nu])%mod; 88 tree[3][nu<<1|1]=(tree[3][nu<<1|1]+3*tree[2][nu<<1|1]*mark1[nu]+3*tree[1][nu<<1|1]*mark1[nu]*mark1[nu]+(r-mid)*mark1[nu]*mark1[nu]*mark1[nu])%mod; 89 tree[2][nu<<1|1]=(tree[2][nu<<1|1]+2*mark1[nu]*tree[1][nu<<1|1]+(r-mid)*mark1[nu]*mark1[nu])%mod; 90 tree[1][nu<<1|1]=(tree[1][nu<<1|1]+mark1[nu]*(r-mid))%mod; 91 mark2[nu<<1|1]=(mark2[nu<<1|1]*mark2[nu])%mod; 92 mark1[nu<<1|1]=(mark1[nu<<1|1]*mark2[nu]+mark1[nu])%mod; 93 mark1[nu]=mark3[nu]=0;mark2[nu]=1; 94 } 95 96 void change(int l,int r,int nu) 97 { 98 if(L<=l&&r<=R) 99 {100 if(b==3)101 {102 mark1[nu]=a;103 mark2[nu]=1;104 mark3[nu]=1;105 tree[1][nu]=a*(r-l+1)%mod;106 tree[2][nu]=(a*a*(r-l+1))%mod;107 tree[3][nu]=(a*a*a*(r-l+1))%mod;108 }109 if(b==2)110 {111 mark1[nu]=(mark1[nu]*a)%mod;112 mark2[nu]=(mark2[nu]*a)%mod;113 tree[1][nu]=(tree[1][nu]*a)%mod;114 tree[2][nu]=(tree[2][nu]*a*a)%mod;115 tree[3][nu]=(tree[3][nu]*a*a*a)%mod;116 }117 if(b==1)118 {119 mark1[nu]=(mark1[nu]+a)%mod;120 tree[3][nu]=(tree[3][nu]+3*tree[2][nu]*a+3*tree[1][nu]*a*a+(r-l+1)*a*a*a)%mod;121 tree[2][nu]=(tree[2][nu]+2*a*tree[1][nu]+(r-l+1)*a*a)%mod;122 tree[1][nu]=(tree[1][nu]+a*(r-l+1))%mod;123 }124 return;125 }126 down(l,r,nu);127 int mid=(l+r)>>1;128 if(L<=mid)129 change(l,mid,nu<<1);130 if(R>=mid+1)131 change(mid+1,r,nu<<1|1);132 up(nu);133 }134 135 long long sum(int l,int r,int nu)136 {137 long long su=0;138 if(L<=l&&r<=R)139 return tree[a][nu];140 down(l,r,nu);141 int mid=(l+r)>>1;142 if(L<=mid)143 su+=sum(l,mid,nu<<1);144 if(R>=mid+1)145 su+=sum(mid+1,r,nu<<1|1);146 su=su%mod;147 return su;148 }
祝AC哟；