记录编号	384216	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016] 数列操作d	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	2.074 s
提交时间	2017-03-17 19:04:45	内存使用	38.66 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN=300010;
const long long mod=1e9+7;
typedef long long LL;

struct Node{
	long long mul;
	long long flag;
	long long sum;
	long long l;
	long long r;
	Node* lch;
	Node* rch;
};

Node N[MAXN<<2];
Node* top=N;

int n;
int m;
int l;
int r;
int x;

void Build(Node*,int,int);
void Add(Node*);
long long Query(Node*);
void PushDown(Node*);
void FastRead(int&);

int Main(){
	freopen("segment.in","r",stdin);
	freopen("segment.out","w",stdout);
	int type;
	FastRead(n);
	FastRead(m);
	Build(top++,1,n+1);
	for(int i=0;i<m;i++){
		FastRead(type);
		FastRead(l);
		FastRead(r);
		r++;
		switch(type){
			case 1:
				FastRead(x);
				Add(N);
			break;
			case 0:
				printf("%lld\n",Query(N)%mod);
			break;
		}
	}
	return 0;
}

inline void PushDown(Node* root){
	if(root->flag){
		root->lch->flag+=root->flag;
		root->rch->flag+=root->flag;
		root->lch->sum+=(root->lch->r-root->lch->l)*root->flag;
		root->rch->sum+=(root->rch->r-root->rch->l)*root->flag;
		root->flag=0;
	}
	if(root->mul){
		root->lch->mul+=root->mul;
		root->rch->mul+=root->mul;
		root->lch->sum+=(1LL*(root->lch->l+root->lch->r-1)*(root->lch->r-root->lch->l)>>1)*root->mul;
		root->rch->sum+=(1LL*(root->rch->l+root->rch->r-1)*(root->rch->r-root->rch->l)>>1)*root->mul;
		root->mul=0;
	}
}

long long Query(Node* root){
	if(l<=root->l&&root->r<=r)
		return root->sum;
	else{
		long long ans=0;
		PushDown(root);
		if(l<root->lch->r)
			ans+=Query(root->lch);
		if(root->rch->l<r)
			ans+=Query(root->rch);
		return ans;
	}
}

void Add(Node* root){
	if(l<=root->l&&root->r<=r){
		root->sum+=((1LL*x*(root->l+root->r-1)*(root->r-root->l)>>1)-1LL*(root->r-root->l)*l*x);
		root->flag-=1LL*l*x;
		root->mul+=x;
		return;
	}
	else{
		PushDown(root);
		if(l<root->lch->r)
			Add(root->lch);
		if(root->rch->l<r)
			Add(root->rch);
		root->sum=root->lch->sum+root->rch->sum;
	}
}

void Build(Node* root,int l,int r){
	root->l=l;
	root->r=r;
	if(r-l==1)
		return;
	else{
		int mid=(l+r)>>1;
		Build(root->lch=top++,l,mid);
		Build(root->rch=top++,mid,r);
	}
}

void FastRead(int& target){
	target=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	while(ch<='9'&&ch>='0'){
		target=target*10+ch-48;
		ch=getchar();
	}
}

int WORKING=Main();
int main(){;}