记录编号	452397	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 数列操作d	最终得分	100
用户昵称	swttc	是否通过	通过
代码语言	C++	运行时间	6.613 s
提交时间	2017-09-19 15:31:27	内存使用	137.64 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#define mid (l+r>>1)
#define ls (o<<1)
#define rs ((o<<1)+1)
#define av 0.5 

using namespace std;

const int MOD=1e9+7;
long long n,m,dep[3000010],ha[3000010],ans,lazc[3000010];
long double lazy[3000010],sum[3000010];
void buildt(int l,int r,int o)
{
	if(l==r){
		return;
	}
	buildt(l,mid,ls);
	buildt(mid+1,r,rs);
	dep[o]=dep[ls]+1;
	return;
}

void pushdown(int l,int r,int o)
{
	if(dep[o]==0||lazy[o]==0) return;
	lazc[ls]+=lazc[o];
	sum[ls]+=(long double)(mid-l+1)*(lazy[o]-(long double)lazc[o]*pow(2,dep[o]-1)*av);
	lazy[ls]+=lazy[o]-(long double)lazc[o]*pow(2,dep[o]-1)*av;
	lazc[rs]+=lazc[o];
	sum[rs]+=(long double)(r-mid)*(lazy[o]+(long double)lazc[o]*pow(2,dep[o]-1)*av);
	lazy[rs]+=lazy[o]+(long double)lazc[o]*pow(2,dep[o]-1)*av;
	lazy[o]=0.00;
	lazc[o]=0;
}

void change(int l,int r,int o,int ll,int rr,int x)
{
	if(l>=ll&&r<=rr){
		if(l==r){
			sum[o]+=(long double)(l-ll)*(long double)x;
		}
		else{
			sum[o]+=(long double)(l-ll+r-ll)/2.0*(long double)(r-l+1)*(long double)x;
			lazy[o]+=(long double)(l-ll+r-ll)/2.0*(long double)x;
			lazc[o]+=x;
		}
		return;
	}
	pushdown(l,r,o);
	if(mid>=ll) change(l,mid,ls,ll,rr,x);
	if(mid<rr) change(mid+1,r,rs,ll,rr,x);
	sum[o]=sum[ls]+sum[rs];
	return;
}

void query(int l,int r,int o,int ll,int rr)
{	 
	if(l>=ll&&r<=rr){
		ans+=(long long)sum[o];
		return;
	}
	pushdown(l,r,o);
	if(mid>=ll) query(l,mid,ls,ll,rr);
	if(mid<rr) query(mid+1,r,rs,ll,rr);
	return;
}

int main()
{
	freopen("segment.in","r",stdin);
	freopen("segment.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	long long temp=1;
	for(int i=1;i<=n;i++){
		if(i>temp){
			temp*=2;
		}
		ha[i]=temp;
	}
	buildt(1,ha[n],1);
	for(int i=1;i<=m;i++){
		char c;
		cin>>c;
		if(c=='1'){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			change(1,ha[n],1,a,b,c);
		}
		else{
			int a,b;
			scanf("%d%d",&a,&b);
			ans=0;
			query(1,ha[n],1,a,b);
			printf("%lld\n",ans%MOD);
		}
	}//system("pause");
	return 0;
}