记录编号	310012	评测结果	AAAAAAAAAA
题目名称	[EZOI 2016]源氏的数学课	最终得分	100
用户昵称	Ezoi_Vermouth	是否通过	通过
代码语言	C++	运行时间	1.682 s
提交时间	2016-09-21 08:19:34	内存使用	9.28 MiB

#include <cstdio>
#include <cstring>
#define ll long long
#define maxn 100001
#define ref(i,x,y)for(ll i=x;i<=y;i++) 
ll n,q,a[maxn];
struct xint{ll x,y,s,lazy;}s[maxn*4];
inline ll read()
{
    char ch=' ';ll digit=0,flag=1;
    while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-')flag=-1;}
    while(ch>='0'&&ch<='9')digit=digit*10+ch-48,ch=getchar();
    return digit*flag;
}
inline void pushup(ll t,ll tt){s[t].s=s[tt].s+s[tt|1].s;}
inline void pushdown(ll t,ll tt)
{
    ll p=s[t].lazy;s[t].lazy=0;
	s[tt].lazy+=p;s[tt|1].lazy+=p;
    s[tt].s+=p*(s[tt].y-s[tt].x+1);
    s[tt|1].s+=p*(s[tt|1].y-s[tt|1].x+1);
}
inline void build(ll x,ll y,ll t)
{
    s[t].x=x;s[t].y=y;
    if(x==y){s[t].s=a[x];return;}
    ll mid=(x+y)>>1,tt=t<<1;
    build(x,mid,tt);
    build(mid+1,y,tt|1);
    pushup(t,tt);
}
inline void add(ll x,ll y,ll t,ll p)
{
    ll mid=(s[t].x+s[t].y)>>1,tt=t<<1;
    if(s[t].lazy)pushdown(t,tt);
    if(x==s[t].x&&y==s[t].y){s[t].s+=(y-x+1)*p;s[t].lazy=p;return;}
    if(mid<x)add(x,y,tt|1,p);else
    if(mid>=y)add(x,y,tt,p);else
    add(x,mid,tt,p),add(mid+1,y,tt|1,p);
    pushup(t,tt);
}
inline ll get(ll x,ll y,ll t)
{
    ll mid=(s[t].x+s[t].y)>>1,tt=t<<1,res=0;
    if(s[t].lazy)pushdown(t,tt);
    if(x==s[t].x&&y==s[t].y)return s[t].s;
    if(mid<x)res=get(x,y,tt|1);else
    if(mid>=y)res=get(x,y,tt);else
    res=get(x,mid,tt)+get(mid+1,y,tt|1);
    pushup(t,tt);return res;
}
inline ll get2(ll x,ll t)
{
	if(x==0)return 0;
	ll mid=(s[t].x+s[t].y)>>1,tt=t<<1,res=0;
	if(s[t].lazy)pushdown(t,tt);
	if(x==s[t].x&&x==s[t].y)return s[t].s;
	if(mid<x)res=get2(x,tt|1);else
	if(mid>=x)res=get2(x,tt);
	pushup(t,tt);return res;
}
int main()
{
    freopen("overwatch.in","r",stdin);
    freopen("overwatch.out","w",stdout);
    n=read();q=read();
    ref(i,1,n)a[i]=read(),a[i]+=a[i-1];
    build(1,n,1);
    ref(i,1,q)
    {
        ll o=read(),x=read(),y=read();
        if(o==1)add(x,n,1,y);else
        if(o==2)printf("%lld\n",get(x,y,1)-get2(x-1,1)*(y-x+1));
    }
}