R - Transformation （线段树&lazy标记）

思路：由于都是对区间进行修改和询问，所以可以用lazy标记该区间是否相等。若不相等总能分成若干个相等小的区间进行求和。具体看代码。

AC代码：

#include<cstdio>
#include<cstring>
using namespace std;
const int N=8e6+5,mod=1e4+7; 
struct node{
	int l,r,lz,s;//这里的a[i].s表示的是这个区间的数等于s 而不是这个区间的总和。 
}a[N];
int n,m,op,x,y,c;
int ksm(int x,int n){ //快速幂板子 
	int ans=1;
	while(n){
		if(n&1) ans=ans*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return ans;
}
void re(int x){
	if(a[x<<1].lz&&a[x<<1|1].lz&&a[x<<1].s==a[x<<1|1].s)
		a[x].lz=1,a[x].s=a[x<<1].s;
	else a[x].lz=0;
}
void pushdown(int x){
	if(a[x].lz){
		a[x<<1].lz=a[x<<1|1].lz=1;
		a[x<<1].s=a[x<<1|1].s=a[x].s;
		a[x].lz=0;
	}
}
void build(int x,int l,int r){
	a[x].l=l,a[x].r=r,a[x].lz=1,a[x].s=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
}
void update(int x,int l,int r,int c){
	if(a[x].lz&&a[x].l>=l&&a[x].r<=r){ //对三个操作的区间修改 
		if(op==1) a[x].s=(a[x].s+c)%mod;
		else if(op==2) a[x].s=(a[x].s*c)%mod;
		else a[x].s=c%mod;
		return;
	}
	pushdown(x);
	int mid=(a[x].l+a[x].r)>>1;
	if(l<=mid) update(x<<1,l,r,c);
	if(r>mid) update(x<<1|1,l,r,c);
	re(x);
} 
int query(int x,int l,int r,int c){
	if(a[x].lz&&a[x].l>=l&&a[x].r<=r) return ksm(a[x].s,c)*(a[x].r-a[x].l+1)%mod;
	else if(a[x].r<l||a[x].l>r) return 0;
	pushdown(x);
	return (query(x<<1,l,r,c)+query(x<<1|1,l,r,c))%mod; 
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		if(!n&&!m) break;
		build(1,1,n);
		while(m--){
			scanf("%d%d%d%d",&op,&x,&y,&c);
			if(op<4) update(1,x,y,c);
			else printf("%d\n",query(1,x,y,c));
		}
	}
	return 0;
}