链接：https://ac.nowcoder.com/acm/contest/26896/1008
来源：牛客网
来源：牛客网
题目描述
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，输出一行表示答案
吐槽：
这一题完全可能出现样例/自己捏的小样例没过，但是能够AC的情况（我第一次提交时就是这样，自己都没想到能过），只能说数据太水了......但是题目还是一道非常好的基础题
题型：
线段树--区间修改与区间查询+一点基础数学
思路（请在掌握基本的线段树区间修改与区间和查询后再看）：
主要难点其实就两个，一是区间的乘法，二是区间的平方和查询，另外两个想必学过一点线段树的区间修改与查询就都可以写出来。
区间的乘法，很显然，要想让lazy既存储加法，又存储乘法，是无法做到的，因此考虑用lazy和lazy2来分别存储加法，乘法的标记。
我们知道，对于一个数，它无论是先乘后加，还是先加后乘，都可以表示成kx+b的形式。但是两种形式也有区别，如果先乘a后加b，那么得到的是ax+b，如果先加b后乘a，那么得到的是a(x+b)=ax+ab
可以看出，对于加法而言(+a)，其对于lazy(加法标记)具有贡献(+a)，对于lazy2(乘法标记)则不具有贡献；而对于乘法而言(*a)，其对于lazy2(乘法标记)具有贡献(*a)，对于lazy(加法标记)也具有贡献(*a)。
所以乘法的事情多开一个lazy2即可解决，注意lazy2初始化为1，区间和直接为ax+b
接下来是区间的平方和
核心公式：x^2——>(ax+b)^2=a*a*x^2+2*a*b*x+b^2
根据这个公式就可以推算出区间平方和了
设tree[]为区间和，tree2[]为区间平方和，那么可得tree2[]=lazy2[]*lazy2[]*tree2[]+2*lazy2[]*lazy[]*tree[]+lazy[]*lazy[];
由此，此题的两个难点已经基本解决，剩下的就是套模板了，难度：属于基础题，但是对于像我这样的小白能够锻炼线段树的基础思维，还是不错的
代码如下，是正确的，一楼那位大佬捏的数据也能够过，而且个人感觉代码应该挺清晰的（借鉴了雨巨大大的模板），适合和自己一样0基础的小白食用。
代码：
#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int N=20000;
int op;
int tree[N*4],a[N],lazy[N*4],lazy2[N*4],tree2[N*4];//lazy:标记（需要时沿着递归顺着往下走就行）
//lazy标记内存储的值是这个节点自己知道，并且其子节点不知道的修改的值总和
void build(int p,int l,int r){
if(l==r){ //区间已经变成单点了
tree[p]=a[l];
tree2[p]=a[l]*a[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p]=tree[p*2]+tree[p*2+1]; //对区间求和
tree2[p]=tree2[p*2]+tree2[p*2+1]; //对区间求平方和
}
void pushdown(int p,int l,int r){
int mid=(l+r)/2;
lazy2[p*2]*=lazy2[p];
lazy2[p*2+1]*=lazy2[p];
lazy[p*2]=(lazy[p*2]*lazy2[p])+lazy[p];
lazy[p*2+1]=(lazy[p*2+1]*lazy2[p])+lazy[p];
tree2[p*2]=(lazy2[p]*lazy2[p]*tree2[p*2])+(2*tree[p*2]*lazy[p]*lazy2[p]+(mid-l+1)*lazy[p]*lazy[p]);
tree2[p*2+1]=(lazy2[p]*lazy2[p]*tree2[p*2+1])+(2*tree[p*2+1]*lazy[p]*lazy2[p]+(r-(mid+1)+1)*lazy[p]*lazy[p]);
tree[p*2]=(tree[p*2]*lazy2[p])+(lazy[p]*(mid-l+1));
tree[p*2+1]=(tree[p*2+1]*lazy2[p])+(lazy[p]*(r-(mid+1)+1));
lazy[p]=0;
lazy2[p]=1;
}
void add(int p,int l,int r,int x,int y,int num){
if(x<=l && y>=r){ //找到了对应节点
tree2[p]+=(2*tree[p]*num+(r-l+1)*num*num);
tree[p]+=num*(r-l+1);
lazy[p]+=num; //加上标记
return;
}
//if(lazy[p] || lazy2[p]>1){
pushdown(p,l,r); //p:节点编号,l,r:区间
//}
int mid=(l+r)/2;
if(x<=mid) add(p*2,l,mid,x,y,num); //左子树与x-y区间有交集
if(y>mid) add(p*2+1,mid+1,r,x,y,num); //右子树与x-y区间有交集
tree[p]=tree[p*2]+tree[p*2+1]; //y加上z之后，值会发生变化，需要对tree上相应的节点的值重新再算一遍
tree2[p]=tree2[p*2]+tree2[p*2+1];
}
void mul(int p,int l,int r,int x,int y,int num){
if(x<=l && y>=r){ //找到了对应节点
tree2[p]=num*num*tree2[p];
tree[p]=num*tree[p];
lazy[p]*=num;
lazy2[p]*=num; //加上标记
return;
}
//if(lazy[p] || lazy2[p]>1){
pushdown(p,l,r); //p:节点编号,l,r:区间
//}
int mid=(l+r)/2;
if(x<=mid) mul(p*2,l,mid,x,y,num); //左子树与x-y区间有交集
if(y>mid) mul(p*2+1,mid+1,r,x,y,num); //右子树与x-y区间有交集
tree[p]=tree[p*2]+tree[p*2+1]; //y加上z之后，值会发生变化，需要对tree上相应的节点的值重新再算一遍
tree2[p]=tree2[p*2]+tree2[p*2+1];
}
int calc(int p,int l,int r,int x,int y){
if(x<=l && y>=r){ //l-r区间包含在x-y区间内部(完全包含，直接加上这个区间的值即可)
if(op==1) return tree[p];
else return tree2[p];
}
//if(lazy[p]){
pushdown(p,l,r);
//}
int mid=(l+r)/2;
int ans=0;
if(x<=mid) ans+=calc(p*2,l,mid,x,y);
if(y>=mid+1) ans+=calc(p*2+1,mid+1,r,x,y);
return ans;
}
signed main(){
int n,m;
scanf("%lld%lld",&n,&m);
for(int i=0;i<=N*4-1;i++) lazy2[i]=1;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
build(1,1,n); //建树：1:编号为几的节点；1,n:当前编号所代表的左右区间边界
while(m--){
int x,y,z;
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld",&x,&y);
printf("%lld\n",calc(1,1,n,x,y));
}else if(op==2){
scanf("%lld%lld",&x,&y);
printf("%lld\n",calc(1,1,n,x,y));
}else if(op==3){
scanf("%lld%lld%lld",&x,&y,&z);
mul(1,1,n,x,y,z);
}else{
scanf("%lld%lld%lld",&x,&y,&z);
add(1,1,n,x,y,z);
}
}
return 0;
}
京公网安备 11010502036488号