hdu4578 Transformation (线段树多种操作)

先呈上原题链接[HDU-4578]
题意：
对于一个区间有4个操作：
1.将a~b都加上c
2.将a~b都乘上c
3.将a~b都变成c
4.查询a~b的每个数的p次方的和。（p=1,2,3）
思路：
虽说是一道很裸的线段树的题，但是却非常考验代码能力。
查询p的取值只有三个，所以维护三棵线段树就行了。
难点在多种操作，每个操作的更新次序是有讲究的，在下推标记的时候一般是先推置数操作，然后推乘法，最后推加法。
坑点：
一定要注意有没有爆范围。。。小心WA到怀疑人生。

good luck and have fun!!!
附上代码：

#include<bits/stdc++.h>
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define test(flag,value) cout<<flag<<":"<<(value)<<endl
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+10;
const int MOD=10007;
const double PI=acos(-1);

int n,m;
int sum[MAXN<<2][4],lazy[MAXN<<2][4];
LL tmp1,tmp2,tmp3;
void init()
{
	for(int i=0;i<=n*4;i++)
	{
		lazy[i][1]=0;
		lazy[i][2]=1;
		lazy[i][3]=0;
		sum[i][1]=sum[i][2]=sum[i][3]=0;
	}
}
void push_up(int rt)
{
	for(int i=1;i<=3;i++)
		sum[rt][i]=sum[rt<<1][i]+sum[rt<<1|1][i];
}

void push_down(int rt,int l,int r)
{
	int m=(l+r)>>1;
	if(lazy[rt][3]!=0)
	{
		tmp1=lazy[rt][3]%MOD;
		sum[rt<<1][1]=(tmp1*(m-l+1))%MOD;
		sum[rt<<1|1][1]=(tmp1*(r-m))%MOD;

		tmp2=(tmp1*lazy[rt][3])%MOD;
		sum[rt<<1][2]=(tmp2*(m-l+1))%MOD;
		sum[rt<<1|1][2]=(tmp2*(r-m))%MOD;

		tmp3=(tmp2*lazy[rt][3])%MOD;
		sum[rt<<1][3]=(tmp3*(m-l+1))%MOD;
		sum[rt<<1|1][3]=(tmp3*(r-m))%MOD;

		lazy[rt<<1][1]=lazy[rt<<1|1][1]=0;
		lazy[rt<<1][2]=lazy[rt<<1|1][2]=1;
		lazy[rt<<1][3]=lazy[rt<<1|1][3]=lazy[rt][3];
		lazy[rt][3]=0;
	}
	if(lazy[rt][2]!=1)
	{
		tmp1=lazy[rt][2]%MOD;
		sum[rt<<1][1]=(sum[rt<<1][1]*tmp1)%MOD;
		sum[rt<<1|1][1]=(sum[rt<<1|1][1]*tmp1)%MOD;

		tmp2=(tmp1*lazy[rt][2])%MOD;
		sum[rt<<1][2]=(sum[rt<<1][2]*tmp2)%MOD;
		sum[rt<<1|1][2]=(sum[rt<<1|1][2]*tmp2)%MOD;

		tmp3=(tmp2*lazy[rt][2])%MOD;
		sum[rt<<1][3]=(sum[rt<<1][3]*tmp3)%MOD;
		sum[rt<<1|1][3]=(sum[rt<<1|1][3]*tmp3)%MOD;

		lazy[rt<<1][2]=(lazy[rt<<1][2]*lazy[rt][2])%MOD;
		lazy[rt<<1|1][2]=(lazy[rt<<1|1][2]*lazy[rt][2])%MOD;
		lazy[rt<<1][1]=(lazy[rt<<1][1]*lazy[rt][2])%MOD;  	//注意下推标记同样要给加法做乘法
		lazy[rt<<1|1][1]=(lazy[rt<<1|1][1]*lazy[rt][2])%MOD;
		lazy[rt][2]=1;
	}
	if(lazy[rt][1]!=0)
	{
		tmp1=lazy[rt][1]%MOD;
		tmp2=(tmp1*lazy[rt][1])%MOD;
		tmp3=(tmp2*lazy[rt][1])%MOD;
		sum[rt<<1][3]=(sum[rt<<1][3]+3*(tmp1*sum[rt<<1][2]%MOD)+3*(tmp2*sum[rt<<1][1]%MOD)+(m-l+1)*tmp3%MOD)%MOD;
		sum[rt<<1|1][3]=(sum[rt<<1|1][3]+3*(tmp1*sum[rt<<1|1][2]%MOD)+3*(tmp2*sum[rt<<1|1][1]%MOD)+(r-m)*tmp3%MOD)%MOD;

		sum[rt<<1][2]=(sum[rt<<1][2]+2*(tmp1*sum[rt<<1][1]%MOD)+(m-l+1)*tmp2%MOD)%MOD;
		sum[rt<<1|1][2]=(sum[rt<<1|1][2]+2*(tmp1*sum[rt<<1|1][1]%MOD)+(r-m)*tmp2%MOD)%MOD;

		sum[rt<<1][1]=(sum[rt<<1][1]+(m-l+1)*tmp1%MOD)%MOD;
		sum[rt<<1|1][1]=(sum[rt<<1|1][1]+(r-m)*tmp1%MOD)%MOD;

		lazy[rt<<1][1]=(lazy[rt<<1][1]+lazy[rt][1])%MOD;
		lazy[rt<<1|1][1]=(lazy[rt<<1|1][1]+lazy[rt][1])%MOD;
		lazy[rt][1]=0;
	}
}
void update(int L,int R,int l,int r,int rt,int type,int val)
{
	if(L<=l&&r<=R)
	{
		tmp1=val;
		tmp2=(tmp1*val)%MOD;
		tmp3=(tmp2*val)%MOD;
		if(type==1)
		{
			lazy[rt][1]=(lazy[rt][1]+val)%MOD;
			sum[rt][3]=(sum[rt][3]+3*(tmp1*sum[rt][2]%MOD)+3*(tmp2*sum[rt][1]%MOD)+(r-l+1)*tmp3%MOD)%MOD;
			sum[rt][2]=(sum[rt][2]+2*(tmp1*sum[rt][1]%MOD)+(r-l+1)*tmp2%MOD)%MOD;
			sum[rt][1]=(sum[rt][1]+(r-l+1)*tmp1%MOD)%MOD;
			return;
		}
 		else if(type==2)
		{
			lazy[rt][1]=(lazy[rt][1]*val)%MOD;
			lazy[rt][2]=(lazy[rt][2]*val)%MOD;
			sum[rt][1]=(sum[rt][1]*tmp1)%MOD;
			sum[rt][2]=(sum[rt][2]*tmp2)%MOD;
			sum[rt][3]=(sum[rt][3]*tmp3)%MOD;
			return;
		}
		else if(type==3)
		{
			lazy[rt][1]=0;
			lazy[rt][2]=1;
			lazy[rt][3]=val;
			sum[rt][1]=(tmp1*(r-l+1))%MOD;
			sum[rt][2]=(tmp2*(r-l+1))%MOD;
			sum[rt][3]=(tmp3*(r-l+1))%MOD;
			return;
		}
		else
			throw("error");
	}
	int m=(l+r)>>1;
	push_down(rt,l,r);
	if(L<=m) update(L,R,l,m,rt<<1,type,val);
	if(R>m)  update(L,R,m+1,r,rt<<1|1,type,val);
	push_up(rt);
}

int query(int L,int R,int l,int r,int rt,int p)
{
	if(L<=l&&r<=R){ return sum[rt][p]%MOD;}
	int m=(l+r)>>1;
	int ret=0;
	push_down(rt,l,r);
	if(m>=L) ret=(ret+query(L,R,l,m,rt<<1,p))%MOD;
	if(m<R)  ret=(ret+query(L,R,m+1,r,rt<<1|1,p))%MOD;
	return ret%MOD;
}

int main(void)
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		if(n==0&&m==0) break;
		while(m--)
		{
			int op,x,y,c;
			scanf("%d%d%d%d",&op,&x,&y,&c);
			if(op!=4)
			{
				update(x,y,1,n,1,op,c);
			}
			else
				printf("%d\n", (query(x,y,1,n,1,c)));
		}
	}
}