记录编号	311590	评测结果	WWWWWWWWWW
题目名称	[EZOI 2016]源氏的数学课	最终得分	0
用户昵称	Go灬Fire	是否通过	未通过
代码语言	C++	运行时间	0.862 s
提交时间	2016-09-24 20:01:13	内存使用	8.02 MiB

#include<cmath>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define LL long long
using namespace std;
const int maxn=1010000;
struct Node{
	int date,lazy;
}a[maxn];
void Init();
void Begin(){
    freopen("overwatch.in","r",stdin);
    freopen("overwatch.out","w",stdout);
}
void End(){fclose(stdin);fclose(stdout);}
int n,m,cnt;
void Update(int rt,int l,int r){
	int x=a[rt].lazy;a[rt].lazy=0;
	int mid=(l+r)>>1;
	a[rt<<1].lazy+=(LL)x*(l-mid+1);a[rt<<1|1].lazy+=x;
	a[rt<<1].date+=(LL)x*(r-mid);a[rt<<1|1].date+=x;
}
LL Get_query(int s,int t,int rt,int l,int r){
	if(s<=l && t>=r)return a[rt].date;
	if(a[rt].lazy)Update(rt,l,r);
	int mid=(l+r)>>1;
	if(t<=mid)return Get_query(s,t,lson);
	if(s>mid)return Get_query(s,t,rson);
	return Get_query(s,t,lson)+Get_query(s,t,rson);
}
void Insert(int s,int t,int z,int rt,int l,int r){
	if(s<=l && t>=r){
		a[rt].date+=(LL)z*(r-l+1);a[rt].lazy+=z;
		return;
	}
	if(a[rt].lazy)Update(rt,l,r);
	int mid=(l+r)>>1;
	if(s<=mid)Insert(s,t,z,lson);
	if(t>mid)Insert(s,t,z,rson);
	a[rt].date=a[rt<<1].date+a[rt<<1|1].date;
}
int main(){
    Begin();
    Init();
    //system("pause");
    End();
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	int tot=0;
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);tot+=x;
		Insert(i,i,tot,1,1,n);
	}
	for(int i=1;i<=m;i++){
		int type,x,y;scanf("%d%d%d",&type,&x,&y);
		if(type==2){
			LL ans;
			if(x==1)ans=Get_query(1,y,1,1,n);
			else ans=Get_query(1,y,1,1,n)-Get_query(1,x-1,1,1,n)*(y-x+2);
			printf("%lld\n",ans);
		}
		else {
			Insert(x,n,y,1,1,n);
		}
	}
}