洛谷 U87561 魔法月饼

题目背景

(9102)年的中秋节注定与往年不同...因为在(9102)年的中秋节前夕，(Seaway)被告知今年的中秋节要新出一款月饼——魔法月饼。

题目描述

魔法月饼有非常奇特的功效——提升(IQ)。这让得(Seaway)蠢蠢欲动。(Seaway)大脑中的思考部分是一段长为(N)的区域，每个智力点有一个初始智力值。魔法月饼可以把(Seaway)思考区域中从(x)到(y)区间的智力值都提升(k)点。但是，每块魔法月饼的具体功效并不相同，也就是说，每块月饼作用的范围和提升的点数都是不一样的。即使如此，(Seaway)还是对这种月饼非常满意。他一共买了(M)块魔法月饼，偶尔，当他大快朵颐的时候，他还想知道自己的(IQ)已经提升多少了。这时他会查询(P)次他大脑中从(x)到(y)的智力和。但是因为他太笨了（不笨的话就不需要吃魔法月饼了），所以他不知道这个和到底是多少。你能帮帮他么？

输入格式

输入的第一行包括(3)个整数：(N，M，P)，意义如题目所示。

第二行包括(N)个用空格隔开的整数，其中第(i)个数字表示(Seaway)大脑中第(i)个智力点的初始值。

接下来的(M+P)行，每行包含一个字母和(2-3)个整数，如果字母为(C)，则后跟(3)个整数(x,y,k)，代表(Seaway)吃了一块月饼，这块月饼把他思考区域中从(x)到(y)区间的智力都提升了(k)点。如果字母为(Q)，则后跟(2)个整数(x,y)，代表(Seaway)想知道目前他大脑中从(x)到(y)的智力和。

输出格式

输出包含(P)行，表示(Seaway)所有询问操作的结果。

提示与说明

数据范围与约定：

对于(30\%)的数据，(1le N le 10,1le M+Ple 10)。

对于(60\%)的数据，(1le Nle 1000,1le M+Ple 10000)。

对于(100\%)的数据，(1le Nle 10^5,1le M+Ple 10^5)。

全部数据保证：(ansle maxlongint)。

题解：

线段树模板题，可能我的背景会对答题出现一些困扰？

~~（我觉得很明白了啊,,,）~~

小声说一句：不开longlong会死的很惨。。。

代码：

#include<cstdio>
#include<iostream>
#define int long long
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=1e5+1;
int n,m,p;
int a[maxn];
int tree[maxn<<2],lazy[maxn<<2];
void build(int pos,int l,int r)
{
    int mid=(l+r)>>1;
    if(l==r)
    {
        tree[pos]=a[l];
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    tree[pos]=tree[rson]+tree[lson];
}
void mark(int pos,int l,int r,int k)
{
    tree[pos]+=(r-l+1)*k;
    lazy[pos]+=k;
}
void pushdown(int pos,int l,int r)
{
    int mid=(l+r)>>1;
    mark(lson,l,mid,lazy[pos]);
    mark(rson,mid+1,r,lazy[pos]);
    lazy[pos]=0;
}
void update(int pos,int l,int r,int x,int y,int k)
{
    int mid=(l+r)>>1;
    if(x<=l && r<=y)
    {
        mark(pos,l,r,k);
        return;
    }   
    pushdown(pos,l,r);
    if(x<=mid)
        update(lson,l,mid,x,y,k);
    if(y>mid)
        update(rson,mid+1,r,x,y,k);
    tree[pos]=tree[lson]+tree[rson];
}
int query(int pos,int l,int r,int x,int y)
{
    int ret=0;
    int mid=(l+r)>>1;
    if(x<=l && r<=y)
        return tree[pos];
    pushdown(pos,l,r);
    if(x<=mid)
        ret+=query(lson,l,mid,x,y);
    if(y>mid)
        ret+=query(rson,mid+1,r,x,y);
    return ret;
}
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&p);
    int q=m+p;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--)
    {
        int x,y,k;
        char ch;
        cin>>ch;
        if(ch=='C')
        {
            scanf("%lld%lld%lld",&x,&y,&k);
            update(1,1,n,x,y,k);
        }
        else
        {
            scanf("%lld%lld",&x,&y);
            printf("%lld
",query(1,1,n,x,y));
        }
    }
    return 0;
}