洛谷 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\%\)的数据，\(1\le N \le 10,1\le M+P\le 10\)。
对于\(60\%\)的数据，\(1\le N\le 1000,1\le M+P\le 10000\)。
对于\(100\%\)的数据，\(1\le N\le 10^5,1\le M+P\le 10^5\)。
全部数据保证：\(ans\le 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\n",query(1,1,n,x,y));
}
}
return 0;
}