本文共 2916 字，大约阅读时间需要 9 分钟。
题目连接：
题意：n个数，初始值为0，4种操作：
1。将某个区间所有值加上另一个值；
2。将区间所有值都乘上另一个值；
3。将区间所有值置为某个值；
4。查询区间中所有值的p次方和。
详细分析：
#pragma comment(linker,"/STACK:102400000,102400000")#include #include #include #include #include #include #include #include #include #include #include #include #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|1using 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 >1; LL res=0; if(L<=m)res+=query(L,R,lson,op); if(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\n",query(x,y,1,n,1,c)); } else { update(x,y,c,1,n,1,op); // printf("%d\n",sum1[1]); } } }}
转载于:https://www.cnblogs.com/lienus/p/4240547.html
