hdu-4578-Transformation-线段树（区间更新区间求和，多lazy,绝世好题）

Time limit 8000 ms
Memory limit 65536 kB

Yuanfang is puzzled with the question below:

There are n integers, a 1, a 2, …, a n. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between a x and a y inclusive. In other words, do transformation a k<---a k+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between a x and a y inclusive. In other words, do transformation a k<---a k×c, k = x,x+1,…,y.
Operation 3: Change the numbers between a x and a y to c, inclusive. In other words, do transformation a k<---c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between a x and a y inclusive. In other words, get the result of a xp+a x+1p+…+a yp.

Yuanfang has no idea of how to do it. So he wants to ask you to help him.

Input

There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines contains an operation. Operation 1 to 3 is in this format: "1 x y c" or "2 x y c" or "3 x y c". Operation 4 is in this format: "4 x y p". (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)

The input ends with 0 0.

Output

For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.

Sample Input

5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3
0 0

Sample Output

307
7489

题解：

这道题思路很清晰但写起来是真的需要功底，需要足够细致和对线段树细节的理解。

首先这道题的本质就是线段树的区间更新和求和，但是求和时要返回的是区间各元素的和，平方和或立方和。肯定不能真的每次都遍历到叶子节点然后求个和，那样百分之二百T。因为只多出来平方和立方两种值，所以很容易想到我们可以多维护个平方值和立方值。

然后因为有加法（lazy1），乘法（lazy2），赋值（lazy3）三种操作所以我们可以用三个lazy（我这里直接lazy存操作的c值，有的人用来标记，其实都一样）。

如果能顺理成章的想到以上的思路，那么这题就完成了三分之一了。

然后需要实现三种运算关于一次方(p1)，平方(p2)，立方值(p3)操作。

加法：

    一次方：区间每个数都加c = 加上 （区间长度len*c）。

    平方：因为（a+c）^2 = a^2 + 2ac + c^2 所以区间每个数都加c之后的平方和 = p2 +2*p1*c + len*Mypow(c,2)。

    立方：因为（a+c）^3 = a^3 + 3a^2c + 3ac^2 + c^3

               所以区间每个数都加c之后的立方和 = p3 + 3*p2*c + 3*p1*Mypow(c,2) + len*Mypow(c,3)。

乘法：

    因为（ac）^n = a^n*c^n;

    所以一次方：p1*c。

    平方：p2*Mypow(c,2)。

    立方：p3*Mypow(c,3)。

赋值：

    这个没啥好说的了吧。

    一次方：len*c。

    平方：len*Mypow(c,2)。

    立方：len*Mypow(c,3)。

到这这题算是完成三分之二了。

最后我们要考虑的是如果有两个甚至三个lazy同时存在咋处理。

因为我们无法通过lazy中存的值看出先后顺序，而运算的顺序不同结果肯定不同所以我们就需要排除顺序的差异。

首先是赋值，如果先进行加法或乘法操作再进行赋值，那么前面的加法乘法操作肯定是没有啥意义的

那么我们可以在给赋值的lazy3赋值的同时清空lazy1和lazy2，这样的话如果lazy1!=0 或 lazy2>1所代表的加法乘法

运算肯定是在赋值操作之后的。通过这样我们就可以放心的让赋值lazy3第一个PushDown了。

同样的先加后乘和先乘后加的区别在于——（a+b）*c ——（a*c + b）——一个是a*c+b*c 一个是 a*c+b。

差距其实就在最后加的那部分，也就是将lazy1向子区间更新时该加b*c还是b的问题。那么当我们进行乘操作时可以判断一下lazy1是否不为0，如果true则代表之前已经有进行加法运算，那么应该将lazy1乘以c。

到此这道题就完成了。

代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
const int MOD = 10007;

struct D{
	int p1,p2,p3;//记录普通，平方，立方的值。 
	int lazy1,lazy2,lazy3;//分别存储加法，乘法，赋值运算的c 
	int len;//记录区间长度。 
}Tree[MAXN*4];

int Mypow(int a,int b){
/*其实这题最多就是立方，所以时间上完全可以不用快速幂
但考虑到pow(10000,3)会超int还是自己写一个自带取余的Mypow吧。*/ 
	int re = 1;
	while(b){
		if(b%2 != 0){
			re *= a;
			re %= MOD;
		}
		a *= a;
		a %= MOD;
		b >>= 1; 
	}
	return re;
}

void Build(int temp , int left , int right){
	Tree[temp].p1 = Tree[temp].p2 = Tree[temp].p3 = 0;
	Tree[temp].lazy1 = Tree[temp].lazy3 = 0;
	Tree[temp].lazy2 = 1;
	Tree[temp].len = right-left+1;
	if(left == right)return;
	int mid = left + (right-left)/2;
	Build(temp<<1,left,mid);
	Build(temp<<1|1,mid+1,right);
}

void Up(int temp){
	Tree[temp].p1 = ( Tree[temp<<1].p1 + Tree[temp<<1|1].p1 )%MOD;
	Tree[temp].p2 = ( Tree[temp<<1].p2 + Tree[temp<<1|1].p2 )%MOD;
	Tree[temp].p3 = ( Tree[temp<<1].p3 + Tree[temp<<1|1].p3 )%MOD;
}

void PushDown(int temp){
	/*这里要按先判断赋值，再判断乘法，最后判断加法的顺序*/
	if(Tree[temp].lazy3){
		Tree[temp<<1].lazy3 = Tree[temp<<1|1].lazy3 = Tree[temp].lazy3;
		Tree[temp<<1].lazy1 = Tree[temp<<1|1].lazy1 = 0;
		Tree[temp<<1].lazy2 = Tree[temp<<1|1].lazy2 = 1;
		Tree[temp<<1].p1 = ( (Tree[temp<<1].len) * (Tree[temp].lazy3) )%MOD;
		Tree[temp<<1].p2 = ( (Tree[temp<<1].len) * Mypow(Tree[temp].lazy3,2) )%MOD;
		Tree[temp<<1].p3 = ( (Tree[temp<<1].len) * Mypow(Tree[temp].lazy3,3) )%MOD;
		Tree[temp<<1|1].p1 = ( (Tree[temp<<1|1].len) * (Tree[temp].lazy3) )%MOD;
		Tree[temp<<1|1].p2 = ( (Tree[temp<<1|1].len) * Mypow(Tree[temp].lazy3,2) )%MOD;
		Tree[temp<<1|1].p3 = ( (Tree[temp<<1|1].len) * Mypow(Tree[temp].lazy3,3) )%MOD;
		Tree[temp].lazy3 = 0;
	}
	if(Tree[temp].lazy2>1){
		Tree[temp<<1].lazy2 *= Tree[temp].lazy2;
		Tree[temp<<1].lazy2 %= MOD;
		if(Tree[temp<<1].lazy1){
			Tree[temp<<1].lazy1 *= Tree[temp].lazy2;
			Tree[temp<<1].lazy1 %= MOD;
		}
		Tree[temp<<1|1].lazy2 *= Tree[temp].lazy2;
		Tree[temp<<1|1].lazy2 %= MOD;
		if(Tree[temp<<1|1].lazy1){
			Tree[temp<<1|1].lazy1 *= Tree[temp].lazy2;
			Tree[temp<<1|1].lazy1 %= MOD;
		}
		Tree[temp<<1].p1 *= Tree[temp].lazy2;
		Tree[temp<<1].p1 %= MOD;
		Tree[temp<<1].p2 *= Mypow(Tree[temp].lazy2,2);
		Tree[temp<<1].p2 %= MOD;
		Tree[temp<<1].p3 *= Mypow(Tree[temp].lazy2,3);
		Tree[temp<<1].p3 %= MOD;
		Tree[temp<<1|1].p1 *= Tree[temp].lazy2;
		Tree[temp<<1|1].p1 %= MOD;
		Tree[temp<<1|1].p2 *= Mypow(Tree[temp].lazy2,2);
		Tree[temp<<1|1].p2 %= MOD;
		Tree[temp<<1|1].p3 *= Mypow(Tree[temp].lazy2,3);
		Tree[temp<<1|1].p3 %= MOD;
		Tree[temp].lazy2 = 1;
	}
	if(Tree[temp].lazy1){
		Tree[temp<<1].lazy1 += Tree[temp].lazy1;
		Tree[temp<<1].lazy1 %= MOD;
		Tree[temp<<1|1].lazy1 += Tree[temp].lazy1;
		Tree[temp<<1|1].lazy1 %= MOD;
		Tree[temp<<1].p3 = ( (Tree[temp<<1].p3) + (3*Tree[temp<<1].p1*Mypow(Tree[temp].lazy1,2))%MOD + (3*Tree[temp<<1].p2*Tree[temp].lazy1)%MOD + (Tree[temp<<1].len*Mypow(Tree[temp].lazy1,3))%MOD )%MOD;
		Tree[temp<<1].p2 = ( (Tree[temp<<1].p2) + (2*Tree[temp<<1].p1*Tree[temp].lazy1)%MOD + (Tree[temp<<1].len*Mypow(Tree[temp].lazy1,2))%MOD )%MOD;
		Tree[temp<<1].p1 = ( (Tree[temp<<1].p1) + (Tree[temp<<1].len*Tree[temp].lazy1)%MOD )%MOD;
		Tree[temp<<1|1].p3 = ( (Tree[temp<<1|1].p3) + (3*Tree[temp<<1|1].p1*Mypow(Tree[temp].lazy1,2))%MOD + (3*Tree[temp<<1|1].p2*Tree[temp].lazy1)%MOD + (Tree[temp<<1|1].len*Mypow(Tree[temp].lazy1,3))%MOD )%MOD;
		Tree[temp<<1|1].p2 = ( (Tree[temp<<1|1].p2) + (2*Tree[temp<<1|1].p1*Tree[temp].lazy1)%MOD + (Tree[temp<<1|1].len*Mypow(Tree[temp].lazy1,2))%MOD )%MOD;
		Tree[temp<<1|1].p1 = ( (Tree[temp<<1|1].p1) + (Tree[temp<<1|1].len*Tree[temp].lazy1)%MOD )%MOD;
		Tree[temp].lazy1 = 0;
	}
}

void Updata(int temp , int left , int right , int ql , int qr , int kind , int value){//kind存储操作种类，value是值 
	if(ql>right && qr<left)return ;
	if(ql<=left && qr>=right){
		//printf("1-------%lld %lld %lld %lld %lld
",left,right,Tree[temp].p1,Tree[temp].p2,Tree[temp].p3);
		if(kind == 3){
			Tree[temp].lazy3 = value;
			Tree[temp].lazy1 = 0;//要记得把加法的lazy清零 
			Tree[temp].lazy2 = 1;//乘法lazy赋值1 
			Tree[temp].p1 = ( (Tree[temp].len) * value )%MOD;
			Tree[temp].p2 = ( (Tree[temp].len) * Mypow(value,2) )%MOD;
			Tree[temp].p3 = ( (Tree[temp].len) * Mypow(value,3) )%MOD;
		}
		else if(kind == 2){
			Tree[temp].lazy2 *= value;
			Tree[temp].lazy2 %= MOD;
			if(Tree[temp].lazy1){
			//如果此时加法lazy不为0，则代表在乘之前有做加法，则要把加的数乘个value。 
				Tree[temp].lazy1 *= value;
				Tree[temp].lazy1 %= MOD;
			}
			Tree[temp].p1 *= value;
			Tree[temp].p1 %= MOD;
			Tree[temp].p2 *= Mypow(value,2);
			Tree[temp].p2 %= MOD;
			Tree[temp].p3 *= Mypow(value,3);
			Tree[temp].p3 %= MOD;
		}
		else if(kind == 1){
			Tree[temp].lazy1 += value;//加法就直接加就好，啥也不用管。 
			Tree[temp].lazy1 %= MOD;
			Tree[temp].p3 = ( (Tree[temp].p3) + (3*Tree[temp].p1*Mypow(value,2))%MOD + (3*Tree[temp].p2*value)%MOD + (Tree[temp].len*Mypow(value,3))%MOD )%MOD;
			Tree[temp].p2 = ( (Tree[temp].p2) + (2*Tree[temp].p1*value)%MOD + (Tree[temp].len*Mypow(value,2))%MOD )%MOD;
			Tree[temp].p1 = ( (Tree[temp].p1) + (Tree[temp].len*value)%MOD )%MOD;
		}
		//printf("2-------%lld %lld %lld %lld %lld
",left,right,Tree[temp].p1,Tree[temp].p2,Tree[temp].p3);
		return ;
	}
	PushDown(temp);
	int mid = left + (right-left)/2;
	if(ql<=mid)Updata(temp<<1,left,mid,ql,qr,kind,value);
	if(qr>mid)Updata(temp<<1|1,mid+1,right,ql,qr,kind,value);
	Up(temp);
}

int Query(int temp , int left , int right , int ql , int qr , int pow){//pow存储返回几次方的值 
 	if(ql>right || qr<left)return 0;
 	if(ql<=left && qr>=right){
 		if(pow == 1)return Tree[temp].p1;
 		else if(pow == 2)return Tree[temp].p2;
 		else if(pow == 3)return Tree[temp].p3;
	}
	PushDown(temp);
	int mid = left + (right-left)/2;
	int sum = 0;
	if(ql<=mid)sum += Query(temp<<1,left,mid,ql,qr,pow);
	if(qr>mid)sum += Query(temp<<1|1,mid+1,right,ql,qr,pow);
	return sum%MOD;
}

int main(){
	
	int N,M;
	int a,b,c,d;
	while(scanf("%d %d",&N,&M) && (N || M)){
		Build(1,1,N);
		while(M--){
			scanf("%d %d %d %d",&a,&b,&c,&d);
			if(a == 4){
				printf("%d
",Query(1,1,N,b,c,d));
			}
			else {
				Updata(1,1,N,b,c,a,d);
			}
		}
	}
	
	return 0;
}



【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/vocaloid01/p/9514104.html