链接：https://ac.nowcoder.com/acm/problem/25879
来源：牛客网
%3Da_%7Bk%7D%5Ctimes%5Csum_%7Bj%3Dk%2B1%7D%5E%7Br%7D%7Ba_%7Bj%7D%7D)
%7D)
来源：牛客网
题目描述
数据总库的信号墙有n个电极插头，每个插头有一个信号ai,
小T可以使在区间[ l,r ]内的所有信号加上一个值k。
对于区间[ l,r ]的信号强度有一个计算公式：
我们定义
则信号强度就为：
你可以认为f(i)就是第i个插头的信号强度。
现在小T一会儿修改信号值，一会儿询问信号强度，你是数据库的管理员，为了不被小TD，所以你要告诉他信号强度是多少。
输入描述:
第一行两个整数n,Q 第二行n个整数代表a 后Q行代表操作： 一操作：1 l r x代表区间[l,r]加x。 二操作：2 l r代表区间询问。
输出描述:
每一行一个数字，表示对于一个二操作的答案。
题型：
线段树--区间修改与区间查询
思路：
（P.S.：本题要求一些数学思维以及转化思维，直接用上面那个公式硬做本人没试过，应该是会TLE的）
这里是结论：答案所求的值等于（[l,r]的区间和的平方-[l,r]区间平方的和）/2
思考过程大致如下（结论懂了就没必要看了，基本都能写）
首先，我们可以看出区间修改是个板子，那么看区间询问
把要求的量，也就是，拆开来写，可以得到其值为：al*(al+1+al+2+...+ar)+al+1*(al+2+...+ar)+...+ar-1*ar;
如果区间询问直接硬算每一个区间的和再加起来，想必是会TLE的，这个时候就要考虑有没有快捷的方法求出这一坨值了，而且最好还是带区间的
我们发现，假设只用区间和来求这一个值，那是无法求出的，所以进一步考虑区间平方和
由于（a+b+c+...+n）2=（a2+b2+...+n2）+2*(a*b+a*c+...a*n+b*c+b*d+...+b*n+...+(n-1)*n);
我们发现，最右边的大括号里面的东西就是所求的答案，所以答案所求的值就等于（[l,r]的区间和的平方-[l,r]区间平方的和）/2
---------------------------下面为区间平方和的求***求区间平方和的话可以直接开始写代码了，因为本题最难的思维转化已经解决了-----------------------------
至于区间平方和的求法，我们可以类比于区间和的求法（如果区间和还不会求的话，这一题建议先放着）
设tree2[p]存储区间平方和
给区间平方和加一个a，相当于x2-->(x+a)2，可以看到差值为2*a*x+a2，加上这个差值即可，即下面代码里的
tree2[p]+=(2*tree[p]*num+num*num*(r-l+1));至于pushdown函数里面，公式也是一样的，就是对应的变量与范围改了一下，即下面代码里的
tree2[p*2]+=2*lazy[p]*tree[p*2]+lazy[p]*lazy[p]*(mid-l+1); tree2[p*2+1]+=2*lazy[p]*tree[p*2+1]+lazy[p]*lazy[p]*(r-(mid+1)+1);
代码：
#include<bits/stdc++.h>
#define int long long int
using namespace std;
const int N=1e5+200;
int tree[N*4],tree2[N*4],lazy[N*4],a[N]; //tree为区间和，tree2为区间平方和
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;
lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
tree2[p*2]+=2*lazy[p]*tree[p*2]+lazy[p]*lazy[p]*(mid-l+1);
tree2[p*2+1]+=2*lazy[p]*tree[p*2+1]+lazy[p]*lazy[p]*(r-(mid+1)+1);
tree[p*2]+=lazy[p]*(mid-l+1);
tree[p*2+1]+=lazy[p]*(r-(mid+1)+1);
lazy[p]=0;
}
void add(int p,int l,int r,int x,int y,int num){
if(x<=l && r<=y){
tree2[p]+=(2*tree[p]*num+num*num*(r-l+1));
tree[p]+=num*(r-l+1);
lazy[p]+=num;
return;
}
if(lazy[p]) pushdown(p,l,r);
int mid=(l+r)/2;
if(x<=mid) add(p*2,l,mid,x,y,num);
if(y>=mid+1) add(p*2+1,mid+1,r,x,y,num);
tree[p]=tree[p*2]+tree[p*2+1];
tree2[p]=tree2[p*2]+tree2[p*2+1];
}
int calc(int p,int l,int r,int x,int y){ //求区间和
if(x<=l && r<=y){
return tree[p];
}
if(lazy[p]) pushdown(p,l,r);
int ans=0;
int mid=(l+r)/2;
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;
}
int calc2(int p,int l,int r,int x,int y){ //求区间平方和
if(x<=l && r<=y){
return tree2[p];
}
if(lazy[p]) pushdown(p,l,r);
int ans=0;
int mid=(l+r)/2;
if(x<=mid) ans+=calc2(p*2,l,mid,x,y);
if(y>=mid+1) ans+=calc2(p*2+1,mid+1,r,x,y);
return ans;
}
signed main(){
int n,q;
scanf("%lld%lld",&n,&q);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
build(1,1,n);
while(q--){
int op,x,y,num;
scanf("%lld",&op);
if(op==1){
scanf("%lld%lld%lld",&x,&y,&num);
add(1,1,n,x,y,num);
}else{
scanf("%lld%lld",&x,&y);
int t1=calc(1,1,n,x,y); //求区间和
int t2=calc2(1,1,n,x,y); //求区间平方和
printf("%lld\n",(t1*t1-t2)/2);
}
}
return 0;
}
京公网安备 11010502036488号