本文主要是介绍HDU 4578 线段树 多lazy操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2013ACM-ICPC杭州赛区全国邀请赛 线段树裸题
bzoj 1798 升级版
add记录 加
mul记录 乘
sum[1] 记录一次方和
sum[2] 记录二次方和
sum[3] 记录三次方和
公式推导出：
sum[3]=(sum[3]+(sqr3(m)*len())%mod + (3*m*sum[2])%mod + (3*sqr2(m)*sum[1])%mod) %mod;
sum[2]=( (2*m*sum[1]%mod) + (sum[2]+sqr2(m)*len()%mod))%mod;
sum[1]= (sum[1]+m*len())%mod;
#include "stdio.h"
#include "string.h"
#include "algorithm"
using namespace std;const int mod=10007;int sqr2(int x)
{return x*x%mod;
}int sqr3(int x)
{return sqr2(x)*x%mod;
}struct segtree
{int l,r, k;int mul,add,sum[4];int mid(){return (l+r)/2;}int len(){return r-l+1;}void init(){mul=1; add=0;}void to_mul(int m){mul=mul*m%mod;add=add*m%mod;sum[1]=sum[1]*m%mod;sum[2]=sum[2]*sqr2(m)%mod;sum[3]=sum[3]*sqr3(m)%mod;}void to_add(int m){add=(add+m)%mod;sum[3]=(sum[3]+(sqr3(m)*len())%mod + (3*m*sum[2])%mod + (3*sqr2(m)*sum[1])%mod) %mod;sum[2]=( (2*m*sum[1]%mod) + (sum[2]+sqr2(m)*len()%mod))%mod;sum[1]= (sum[1]+m*len())%mod;}
}data[400010];void build (int l,int r,int k)
{data[k].l=l;data[k].r=r;data[k].init();memset(data[k].sum,0,sizeof(data[k].sum));if (l==r)return ;int mid=data[k].mid();build(l,mid,k*2);build(mid+1,r,k*2+1);
}void pushdown(int k)
{data[k*2].to_mul(data[k].mul);data[k*2].to_add(data[k].add);data[k*2+1].to_mul(data[k].mul);data[k*2+1].to_add(data[k].add);data[k].init();
}
void updata(int l,int r,int k,int mul,int add)
{if (data[k].l==l && data[k].r==r){data[k].to_mul(mul);data[k].to_add(add);return ;}pushdown(k);int mid=data[k].mid();if (r<=mid) updata(l,r,k*2,mul,add);elseif (l>mid) updata(l,r,k*2+1,mul,add);else{updata(l,mid,k*2,mul,add);updata(mid+1,r,k*2+1,mul,add);}data[k].sum[1]=(data[k*2].sum[1]+data[k*2+1].sum[1])%mod;data[k].sum[2]=(data[k*2].sum[2]+data[k*2+1].sum[2])%mod;data[k].sum[3]=(data[k*2].sum[3]+data[k*2+1].sum[3])%mod;
}int query(int l,int r,int k,int c)
{if (data[k].l==l && data[k].r==r)return data[k].sum[c];int mid=data[k].mid();pushdown(k);if (r<=mid) return query(l,r,k*2,c);elseif (l>mid) return query(l,r,k*2+1,c);elsereturn (query(l,mid,k*2,c)+query(mid+1,r,k*2+1,c))%mod;
}
int main()
{int n,m,op,a,b,c;while (scanf("%d%d",&n,&m)!=EOF){if (n==0 && m==0) break;build(1,n,1);while (m--){scanf("%d%d%d%d",&op,&a,&b,&c);if (op==1)updata(a,b,1,1,c);if (op==2)updata(a,b,1,c,0);if (op==3)updata(a,b,1,0,c);if (op==4)printf("%d\n",query(a,b,1,c));}}return 0;}
这篇关于HDU 4578 线段树 多lazy操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
