[OpenJudge] 平方和

时间:2022-03-03 09:38:54

平方和

总时间限制: 3000ms 内存限制: 65536kB

描述

给出n(1<=n<=500000)个数字,下标从1开始

执行m(1<=m<=500000)次操作,操作可分为两种:

1 l r x:将区间[l,r]内的每个数加上x  1<=l<=r<=n -100<=x<=100

2 l r:输出区间[l,r]内每个数平方之和

输入
多组输入
第一行两个整数n m
第二行n个整数
余下m行表示m个操作意义叙述于上
输出
对应每个2操作输出相应的值
样例输入
5 3
1 1 1 1 1
2 1 5
1 1 5 1
2 1 5
样例输出
5
20 线段树成段更新
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 500005
#define ll long long ll add[N<<];
ll sq[N<<];
ll sum[N<<]; void pushup(int rt)
{
sum[rt]=sum[rt<<]+sum[rt<<|];
sq[rt]=sq[rt<<]+sq[rt<<|];
}
void pushdown(int l,int r,int rt)
{
if(add[rt])
{
int m=(l+r)>>;
add[rt<<]+=add[rt];
add[rt<<|]+=add[rt]; sq[rt<<]+=(*add[rt]*sum[rt<<]+(m-l+)*add[rt]*add[rt]);
sq[rt<<|]+=(*add[rt]*sum[rt<<|]+(r-m)*add[rt]*add[rt]); sum[rt<<]+=(m-l+)*add[rt];
sum[rt<<|]+=(r-m)*add[rt];
add[rt]=;
}
}
void build(int l,int r,int rt)
{
add[rt]=;
if(l==r)
{
scanf("%d",&sum[rt]);
sq[rt]=sum[rt]*sum[rt];
return;
}
int m=(l+r)>>;
build(l,m,rt<<);
build(m+,r,rt<<|);
pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c)
{
if(l==L && r==R)
{
add[rt]+=c;
sq[rt]+=*sum[rt]*c+(r-l+)*c*c;
sum[rt]+=(r-l+)*c;
return;
}
int m=(l+r)>>;
pushdown(l,r,rt);
if(R<=m) update(l,m,rt<<,L,R,c);
else if(L>m) update(m+,r,rt<<|,L,R,c);
else
{
update(l,m,rt<<,L,m,c);
update(m+,r,rt<<|,m+,R,c);
}
pushup(rt);
}
ll query(int l,int r,int rt,int L,int R)
{
if(l==L && r==R)
{
return sq[rt];
}
int m=(l+r)>>;
pushdown(l,r,rt);
if(R<=m) return query(l,m,rt<<,L,R);
else if(L>m) return query(m+,r,rt<<|,L,R);
else return query(l,m,rt<<,L,m)+query(m+,r,rt<<|,m+,R);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
build(,n,);
while(m--)
{
int op,a,b,c;
scanf("%d",&op);
if(op==)
{
scanf("%d%d%d",&a,&b,&c);
update(,n,,a,b,c);
}
else
{
scanf("%d%d",&a,&b);
printf("%lld\n",query(,n,,a,b));
}
}
}
return ;
}

[OpenJudge] 平方和的更多相关文章

  1. 【OpenJudge 8463】Stupid cat &amp&semi; Doge

    http://noi.openjudge.cn/ch0204/8463/ 挺恶心的一道简单分治. 一开始准备非递归. 大if判断,后来发现代码量过长,决定大打表判断后继情况,后来发现序号不对称. 最后 ...

  2. 【OpenJudge 191】【POJ 1189】钉子和小球

    http://noi.openjudge.cn/ch0405/191/ http://poj.org/problem?id=1189 一开始忘了\(2^{50}\)没超long long差点写高精度Q ...

  3. 【OpenJudge 1665】完美覆盖

    http://noi.openjudge.cn/ch0405/1665/?lang=zh_CN 状压水题,手动转移 #include<cstdio> #include<cstring ...

  4. 【OpenJudge 1793】矩形覆盖

    http://noi.openjudge.cn/ch0405/1793/ 好虐的一道题啊. 看数据范围,一眼状压,然后调了好长时间QwQ 很容易想到覆盖的点数作为状态,我用状态i表示至少覆盖状态i表示 ...

  5. OpenJudge 2990&colon;符号三角形 解析报告

    2990:符号三角形 总时间限制:  1000ms       内存限制:  65536kB 描述 符号三角形的第1行有n个由“+”和”-“组成的符号 ,以后每行符号比上行少1个,2个同号下面是”+“ ...

  6. AC日记——与7无关的数 openjudge 1&period;5 39

    39:与7无关的数 总时间限制:  1000ms 内存限制:  65536kB 描述 一个正整数,如果它能被7整除,或者它的十进制表示法中某一位上的数字为7,则称其为与7相关的数.现求所有小于等于n( ...

  7. noi题库(noi&period;openjudge&period;cn) 1&period;5编程基础之循环控制T36——T45

    T36 计算多项式的值 描述 假定多项式的形式为xn+xn-1+-+x2+x+1,请计算给定单精度浮点数x和正整数n值的情况下这个多项式的值. 输入 输入仅一行,包括x和n,用单个空格隔开.x在flo ...

  8. hdu 2007 - 平方和与立方和

    题目大意: 给定一段连续的整数,求出他们中所有偶数的平方和以及所有奇数的立方和. 解答: 坑你没商量!要考虑输入数a,b的大小.如果a>b,需要交换a,b的值. 1: #include<s ...

  9. OpenJudge 7624 山区建小学

    在openjudge似乎无法凭题号搜到题...? 总时间限制:  1000ms  内存限制:  65536kB 描述 *在某山区修建了一条道路,恰好穿越总共m个村庄的每个村庄一次,没有回路或交叉,任 ...

随机推荐

  1. &period;framework使用注意、静态库配置及构架合成

    使用注意: 1.项目中使用的framework中包含了资源文件时,需要手动添加该framework中的资源文件 2.由于动态库(framework默认生成为动态库)不能上架,我们在生成的时候需要修改为 ...

  2. 由&OpenCurlyDoubleQuote;Jasperrpeorts 4&period;1&period;2升级到5&period;1&period;2对flex项目的解析”到AS3 带命名空间的XML的操作

    原文同步至:http://www.waylau.com/from-jasperrpeorts-4-1-2-upgraded-to-5-1-2-parsing-of-flex-projects-to-t ...

  3. nginx配置-为没有后缀的文件(实际上是有html文件)以html形式打开

    location ~ index.php@ { add_header content-type "text/html"; }

  4. Linux命令之pwd

    从今天开始,我会慢慢的把学习Linux过程中的一些命令简单的介绍一下,只是简单的介绍. 我的系统是Ubantu pwd命令 用处:查看当前所在的目录 用法:直接在终端里面输入pwd就好了 示例:

  5. AngularJS实战之cookie的读取

    <!DOCTYPE html> <html ng-controller="cookies_controller"> <head> <tit ...

  6. Actor模式初步入门

    Actor模型概念 Actor模型为并行而生,简单说是未解决高并发的一种编程思路.在Actor模型中,主角是Actor,类似一种worker,Actor彼此之间直接发送消息,不需要经过什么中介,消息是 ...

  7. 使用Axure RP原型设计实践02&comma;自定义部件以及熟悉与部件相关面板

    本篇体验在Axure中自定义部件,并熟悉Widget Interations and Notes面板,Widget Properties and Style面板,Widget Manager面板. 在 ...

  8. JavaScript中的方法、方法引用和参数

    首先,我们来看一段代码,如果觉得不甚明白的,则本文会对你有益: var player = function (e) {             return (function f(m) {      ...

  9. request&period;getParameterMap&lpar;&rpar;获得Map中的数据

    今天使用request.getParameterMap()获得Map中的数据时,使用        Map map=request.getParameterMap();               i ...

  10. Android开发日记(五)

    从服务器端传递多个数据 先在服务器端设置cs文件 using Newtonsoft.Json; using Newtonsoft.Json.Linq; using System; using Syst ...