题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4578
题意：n个数，初始值为0，4种操作：
1。将某个区间所有值加上另一个值；
2。将区间所有值都乘上另一个值；
3。将区间所有值置为某个值；
4。查询区间中所有值的p次方和。
详细分析：http://www.cnblogs.com/GBRgbr/archive/2013/08/13/3254442.html
#pragma comment(linker,"/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <cstdlib> #include <stack> #include <vector> #include <set> #include <map> #define LL long long #define mod 10007 #define inf 0x3f3f3f3f #define N 100010 #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; LL sum1[N<<2],sum2[N<<2],sum3[N<<2]; LL mul[N<<2],add[N<<2]; void Pushup(int rt) { sum1[rt]=(sum1[rt<<1]+sum1[rt<<1|1])%mod; sum2[rt]=(sum2[rt<<1]+sum2[rt<<1|1])%mod; sum3[rt]=(sum3[rt<<1]+sum3[rt<<1|1])%mod; } void Pushdown(int rt,int len) { if(mul[rt]!=1) { mul[rt<<1]=mul[rt<<1]*mul[rt]%mod; mul[rt<<1|1]=mul[rt<<1|1]*mul[rt]%mod; add[rt<<1]=add[rt<<1]*mul[rt]%mod; add[rt<<1|1]=add[rt<<1|1]*mul[rt]%mod; LL u=mul[rt]*mul[rt]%mod,v=mul[rt]*mul[rt]*mul[rt]%mod; sum1[rt<<1]=sum1[rt<<1]*mul[rt]%mod; sum1[rt<<1|1]=sum1[rt<<1|1]*mul[rt]%mod; sum2[rt<<1]=sum2[rt<<1]*u%mod; sum2[rt<<1|1]=sum2[rt<<1|1]*u%mod; sum3[rt<<1]=sum3[rt<<1]*v%mod; sum3[rt<<1|1]=sum3[rt<<1|1]*v%mod; mul[rt]=1; } if(add[rt]!=0) { add[rt<<1]=(add[rt<<1]+add[rt])%mod; add[rt<<1|1]=(add[rt<<1|1]+add[rt])%mod; LL u=add[rt]*add[rt]%mod,v=add[rt]*add[rt]*add[rt]%mod; LL t1=sum1[rt<<1],t2=sum1[rt<<1|1]; LL t3=sum2[rt<<1],t4=sum2[rt<<1|1]; sum1[rt<<1]=(sum1[rt<<1]+(len-(len>>1))*add[rt])%mod; sum1[rt<<1|1]=(sum1[rt<<1|1]+(len>>1)*add[rt])%mod; sum2[rt<<1]=(sum2[rt<<1]+(len-(len>>1))*u+t1*add[rt]*2)%mod; sum2[rt<<1|1]=(sum2[rt<<1|1]+(len>>1)*u+t2*add[rt]*2)%mod; sum3[rt<<1]=(sum3[rt<<1]+(len-(len>>1))*v+t3*add[rt]*3+3*u*t1)%mod; sum3[rt<<1|1]=(sum3[rt<<1|1]+(len>>1)*v+t4*add[rt]*3+3*u*t2)%mod; add[rt]=0; } } void build(int l,int r,int rt) { sum1[rt]=sum2[rt]=sum3[rt]=0; mul[rt]=1;add[rt]=0; if(l==r)return; int m=(l+r)>>1; build(lson); build(rson); } void update(int L,int R,LL c,int l,int r,int rt,int op) { if(L<=l&&r<=R) { LL u=c*c%mod,v=c*c*c%mod; LL len=r-l+1; if(op==1) { LL t1=sum1[rt],t2=sum2[rt]; add[rt]+=c;add[rt]%=mod; sum1[rt]=(sum1[rt]+len*c)%mod; sum2[rt]=(sum2[rt]+2*t1*c+len*u)%mod; sum3[rt]=(sum3[rt]+len*v+3*c*t2+3*u*t1)%mod; } else if(op==2) { mul[rt]*=c;mul[rt]%=mod; add[rt]*=c;add[rt]%=mod; sum1[rt]=sum1[rt]*c%mod; sum2[rt]=sum2[rt]*u%mod; sum3[rt]=sum3[rt]*v%mod; } else { add[rt]=c;mul[rt]=0; sum1[rt]=len*c%mod; sum2[rt]=len*u%mod; sum3[rt]=len*v%mod; } return; } Pushdown(rt,r-l+1); int m=(l+r)>>1; if(L<=m)update(L,R,c,lson,op); if(m<R)update(L,R,c,rson,op); Pushup(rt); } LL query(int L,int R,int l,int r,int rt,int op) { if(L<=l&&r<=R) { if(op==1)return sum1[rt]; else if(op==2)return sum2[rt]; else return sum3[rt]; } Pushdown(rt,r-l+1); int m=(l+r)>>1; LL res=0; if(L<=m)res+=query(L,R,lson,op); if(m<R)res+=query(L,R,rson,op); return res%mod; } int main() { int n,m; int op,x,y,c; while(scanf("%d%d",&n,&m)>0) { if(m+n==0)break; build(1,n,1); while(m--) { scanf("%d%d%d%d",&op,&x,&y,&c); if(op==4) { printf("%I64d ",query(x,y,1,n,1,c)); } else { update(x,y,c,1,n,1,op); // printf("%d ",sum1[1]); } } } }