<题目链接>
qn姐姐最好了~
qn姐姐给你了一个长度为n的序列还有m次操作让你玩，
1 l r 询问区间[l,r]内的元素和
2 l r 询问区间[l,r]内的元素的平方 和
3 l r x 将区间[l,r]内的每一个元素都乘上x
4 l r x 将区间[l,r]内的每一个元素都加上x
输入描述:
第一行两个数n,m
接下来一行n个数表示初始序列
就下来m行每行第一个数为操作方法opt，
若opt=1或者opt=2，则之后跟着两个数为l,r
若opt=3或者opt=4，则之后跟着三个数为l,r,x
操作意思为题目描述里说的
输出描述:
对于每一个操作1,2，输出一行表示答案
输入
5 6
1 2 3 4 5
1 1 5
2 1 5
3 1 2 1
4 1 3 2
1 1 4
2 2 3
输出
15
55
16
41
备注:
对于100%的数据 n=10000,m=200000 (注意是等于号) 保证所有询问的答案在long long 范围内 解题分析：
本题主要的难点在于，对区间进行加或者乘上一个数后，如何快速的维护每个节点的sum 和pfh(区间所有数平方和) 值，如果仅仅是对区间的每个节点进行暴力单点更新的话，毫无疑问会超时。所以我们必须对区间整体修改，而且我们要想到，在区间的维度上，是可以对该区间的每个数平方和进行修改的，它并不像开根号一样，必须要下放到每个叶子节点，对具体的数进行开根。区间修改pfh值时，只需要利用平方和展开式，就能很容易的对区间平方和进行修改。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; #define Lson rt<<1,l,mid
#define Rson rt<<1|1,mid+1,r
typedef long long ll;
const int M = 1e4+;
ll n,m,arr[M];
struct Tree{
ll sum,pfh,add,mul;
}tr[M<<];
void Pushup(ll rt){
tr[rt].sum=tr[rt<<].sum+tr[rt<<|].sum;
tr[rt].pfh=tr[rt<<].pfh+tr[rt<<|].pfh; //pfh记录的是该区间所有元素的平方和
}
void Pushdown(ll rt,ll len){ //mul和add相当于两个lazy标记
if(tr[rt].mul!=){
ll tmp=tr[rt].mul;
tr[rt<<].sum*=tmp,tr[rt<<|].sum*=tmp;
tr[rt<<].pfh=tr[rt<<].pfh*tmp*tmp,tr[rt<<|].pfh=tr[rt<<|].pfh*tmp*tmp; //相当于对该区间的每个数都进行平方
tr[rt<<].mul*=tmp,tr[rt<<|].mul*=tmp; //这几个标记都要*mul
tr[rt<<].add*=tmp,tr[rt<<|].add*=tmp;
tr[rt].mul=;
}
if(tr[rt].add){
ll tmp=tr[rt].add;
tr[rt<<].pfh=tr[rt<<].pfh+*tmp*tr[rt<<].sum+tmp*tmp*(len-(len>>)); //注意这里，要将更新pfh的语句放在更新sum的语句之前
tr[rt<<|].pfh=tr[rt<<|].pfh+*tmp*tr[rt<<|].sum+tmp*tmp*(len>>);
tr[rt<<].sum+=tmp*(len-(len>>)),tr[rt<<|].sum+=tmp*(len>>);
tr[rt<<].add+=tmp,tr[rt<<|].add+=tmp;
tr[rt].add=;
}
}
void build(ll rt,ll l,ll r){
tr[rt].add=,tr[rt].mul=;
if(l==r){
tr[rt].sum=arr[l],tr[rt].pfh=arr[l]*arr[l];
return;
}
ll mid=(l+r)>>;
build(Lson);
build(Rson);
Pushup(rt);
}
void update1(ll rt,ll l,ll r,ll L,ll R,ll c){
if(L<=l&&r<=R){
tr[rt].sum*=c,tr[rt].add*=c,tr[rt].mul*=c;
tr[rt].pfh*=tr[rt].pfh*c*c;
return;
}
Pushdown(rt,r-l+);
ll mid=(l+r)>>;
if(L<=mid)update1(Lson,L,R,c);
if(R>mid)update1(Rson,L,R,c);
Pushup(rt);
}
void update2(ll rt,ll l,ll r,ll L,ll R,ll c){
if(L<=l&&r<=R){
tr[rt].pfh=tr[rt].pfh+*c*tr[rt].sum+c*c*(r-l+); //注意这里，要将更新pfh的语句放在更新sum的语句之前
tr[rt].add+=c;
tr[rt].sum+=c*(r-l+);
return;
}
Pushdown(rt,r-l+);
ll mid=(l+r)>>;
if(L<=mid)update2(Lson,L,R,c);
if(R>mid)update2(Rson,L,R,c);
Pushup(rt);
}
ll query(ll rt,ll l,ll r,ll L,ll R,ll ty){
if(L<=l&&r<=R){
if(ty==)return tr[rt].sum;
else return tr[rt].pfh;
}
Pushdown(rt,r-l+);
ll mid=(l+r)>>;
ll ans=;
if(L<=mid)ans+=query(Lson,L,R,ty);
if(R>mid)ans+=query(Rson,L,R,ty);
return ans;
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++)scanf("%lld",&arr[i]);
build(,,n);
while(m--){
ll op,x,y,c;
scanf("%lld%lld%lld",&op,&x,&y);
if(op==||op==){
printf("%lld\n",query(,,n,x,y,op));
}
else{
scanf("%lld",&c);
if(op==)update1(,,n,x,y,c);
else update2(,,n,x,y,c);
}
}
return ;
}
2018-10-05