这里以3次方来举例讲一下这题的做法，其它维类似。
如果要求某一个值的3次方那么sum = t^3,设t = x+y。那也就是sum = (x+y)^3.
假如我让每个数都加z t = x+y+z，我可以让新的y = y+z,这里发现新来的总会加在y上，那么可以给他一个延迟，slz，
那么新的值t = t + slz,再看如果让每个数都乘k，t = (x+y)*k = xk+yk.可以看出刚才的slz = slz*k; 另外发现系数会跟着变换，可以给他一个延迟，mlz。
那么一个数t = (mlz*x+slz)^3 = mlz^3*x^3+2*mlz^2*slz*x^2+2*mlz*slz^2*x+x^3.
如果求一段这样的和的话，会发现整体就是k1*原本x^3的和+k2*原本x^2的和+k1原本x^1的和 +（r-l+1)*x^3;
这样就可以分别保存3维的和。
把某一段的值设置为v的时候，可以使mlz =0 slz = v.
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set> 10 using namespace std; 11 #define N 100000 12 #define LL __int64 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 const int mod = 10007; 18 int slz[N<<2],mlz[N<<2];//lz[N<<2]; 19 LL s[N<<2][4]; 20 int p[10100][4]; 21 void init() 22 { 23 int i,j; 24 for(i = 0; i <= 10017 ; i++) 25 { 26 p[i][1] = i; 27 for(j = 2 ; j <= 3 ; j++) 28 p[i][j] = (p[i][j-1]*i)%mod; 29 } 30 } 31 void up(int w) 32 { 33 for(int i = 1; i <= 3 ; i++) 34 s[w][i] = (s[w<<1][i]+s[w<<1|1][i])%mod; 35 } 36 void build(int l,int r,int w) 37 { 38 mlz[w] = 1; 39 slz[w] = 0; 40 //lz[w] = 0; 41 if(l==r) 42 { 43 for(int i = 1; i <= 3 ; i++) 44 s[w][i] = 0; 45 return ; 46 } 47 int m = (l+r)>>1; 48 build(l,m,w<<1); 49 build(m+1,r,w<<1|1); 50 up(w); 51 } 52 void down(int w,int m) 53 { 54 55 if(mlz[w]!=1||slz[w]!=0) 56 { 57 mlz[w<<1] = (mlz[w<<1]*mlz[w])%mod; 58 slz[w<<1] = (mlz[w]*slz[w<<1]+slz[w])%mod; 59 mlz[w<<1|1] = (mlz[w<<1|1]*mlz[w])%mod; 60 slz[w<<1|1] = (mlz[w]*slz[w<<1|1]+slz[w])%mod; 61 62 63 int x1 ,x2,x3,y1,y2,y3; 64 x1 = mlz[w]; y1 = slz[w]; 65 x2 = p[x1][2]; y2 = p[y1][2]; 66 x3 = p[x1][3]; y3 = p[y1][3]; 67 s[w<<1][3] = (x3*s[w<<1][3]+(3*x2*y1)%mod*s[w<<1][2]+(3*x1*y2)%mod*s[w<<1][1]+y3*(m-m/2))%mod; 68 s[w<<1|1][3] = (x3*s[w<<1|1][3]+(3*x2*y1)%mod*s[w<<1|1][2]+(3*x1*y2)%mod*s[w<<1|1][1]+y3*(m/2))%mod; 69 s[w<<1][2] = (x2*s[w<<1][2]+(2*x1*y1)%mod*s[w<<1][1]+y2*(m-m/2))%mod; 70 s[w<<1|1][2] = (x2*s[w<<1|1][2]+(2*x1*y1)%mod*s[w<<1|1][1]+y2*(m/2))%mod; 71 s[w<<1][1] = (x1*s[w<<1][1]+y1*(m-m/2))%mod; 72 s[w<<1|1][1] = (x1*s[w<<1|1][1]+y1*(m/2))%mod; 73 mlz[w] = 1; 74 slz[w] = 0; 75 } 76 } 77 void update(int f,int c,int a,int b,int l,int r,int w) 78 { 79 if(a<=l&&b>=r) 80 { 81 if(f==3) 82 { 83 84 85 mlz[w] = 0; 86 slz[w] = c; 87 for(int i = 1; i <= 3 ; i++) 88 s[w][i] = (p[c][i]*(r-l+1))%mod; 89 90 } 91 else if(f==1) 92 { 93 94 slz[w]=(slz[w]+c)%mod; 95 s[w][3] = ((s[w][3]+3*s[w][2]*c+3*s[w][1]*c*c)%mod+(LL)c*c*c*(r-l+1))%mod; 96 s[w][2] = ((s[w][2]+2*c*s[w][1])%mod+(LL)c*c*(r-l+1))%mod; 97 s[w][1] = s[w][1]+c*(r-l+1); s[w][1]%=mod; 98 } 99 else if(f==2) 100 { 101 102 mlz[w] *= c;mlz[w]%=mod; 103 slz[w] *= c;slz[w]%=mod; 104 // } 105 //cout<<l<<" "<<r<<" "<<s[w][2]<<endl; 106 s[w][3] = (s[w][3]*c*c*c)%mod; 107 s[w][2] = (s[w][2]*c*c)%mod; 108 s[w][1] = (c*s[w][1])%mod; 109 //cout<<l<<" "<<r<<" "<<s[w][2]<<endl; 110 } 111 return ; 112 } 113 down(w,r-l+1); 114 int m = (l+r)>>1; 115 if(a<=m) 116 update(f,c,a,b,l,m,w<<1); 117 if(b>m) update(f,c,a,b,m+1,r,w<<1|1); 118 up(w); 119 } 120 LL query(int f,int a,int b,int l,int r,int w) 121 { 122 if(a<=l&&b>=r) 123 { 124 return s[w][f]; 125 } 126 down(w,r-l+1); 127 int m = (l+r)>>1; 128 LL res=0; 129 if(a<=m) res+=query(f,a,b,l,m,w<<1); 130 res%=mod; 131 if(b>m) res+=query(f,a,b,m+1,r,w<<1|1); 132 res%=mod; 133 return res; 134 } 135 int main() 136 { 137 int n,m,i; 138 int k,x,y,c; 139 init(); 140 while(scanf("%d%d",&n,&m)&&n&&m) 141 { 142 build(1,n,1); 143 for(i = 1 ;i <= m; i++) 144 { 145 scanf("%d%d%d%d",&k,&x,&y,&c); 146 if(k<=3) 147 update(k,c,x,y,1,n,1); 148 else 149 printf("%I64d ",(query(c,x,y,1,n,1))%mod); 150 } 151 } 152 return 0; 153 }