平方和
总时间限制: 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] 平方和的更多相关文章
-
【OpenJudge 8463】Stupid cat &; Doge
http://noi.openjudge.cn/ch0204/8463/ 挺恶心的一道简单分治. 一开始准备非递归. 大if判断,后来发现代码量过长,决定大打表判断后继情况,后来发现序号不对称. 最后 ...
-
【OpenJudge 191】【POJ 1189】钉子和小球
http://noi.openjudge.cn/ch0405/191/ http://poj.org/problem?id=1189 一开始忘了\(2^{50}\)没超long long差点写高精度Q ...
-
【OpenJudge 1665】完美覆盖
http://noi.openjudge.cn/ch0405/1665/?lang=zh_CN 状压水题,手动转移 #include<cstdio> #include<cstring ...
-
【OpenJudge 1793】矩形覆盖
http://noi.openjudge.cn/ch0405/1793/ 好虐的一道题啊. 看数据范围,一眼状压,然后调了好长时间QwQ 很容易想到覆盖的点数作为状态,我用状态i表示至少覆盖状态i表示 ...
-
OpenJudge 2990:符号三角形 解析报告
2990:符号三角形 总时间限制: 1000ms 内存限制: 65536kB 描述 符号三角形的第1行有n个由“+”和”-“组成的符号 ,以后每行符号比上行少1个,2个同号下面是”+“ ...
-
AC日记——与7无关的数 openjudge 1.5 39
39:与7无关的数 总时间限制: 1000ms 内存限制: 65536kB 描述 一个正整数,如果它能被7整除,或者它的十进制表示法中某一位上的数字为7,则称其为与7相关的数.现求所有小于等于n( ...
-
noi题库(noi.openjudge.cn) 1.5编程基础之循环控制T36——T45
T36 计算多项式的值 描述 假定多项式的形式为xn+xn-1+-+x2+x+1,请计算给定单精度浮点数x和正整数n值的情况下这个多项式的值. 输入 输入仅一行,包括x和n,用单个空格隔开.x在flo ...
-
hdu 2007 - 平方和与立方和
题目大意: 给定一段连续的整数,求出他们中所有偶数的平方和以及所有奇数的立方和. 解答: 坑你没商量!要考虑输入数a,b的大小.如果a>b,需要交换a,b的值. 1: #include<s ...
-
OpenJudge 7624 山区建小学
在openjudge似乎无法凭题号搜到题...? 总时间限制: 1000ms 内存限制: 65536kB 描述 *在某山区修建了一条道路,恰好穿越总共m个村庄的每个村庄一次,没有回路或交叉,任 ...
随机推荐
-
.framework使用注意、静态库配置及构架合成
使用注意: 1.项目中使用的framework中包含了资源文件时,需要手动添加该framework中的资源文件 2.由于动态库(framework默认生成为动态库)不能上架,我们在生成的时候需要修改为 ...
-
由“Jasperrpeorts 4.1.2升级到5.1.2对flex项目的解析”到AS3 带命名空间的XML的操作
原文同步至:http://www.waylau.com/from-jasperrpeorts-4-1-2-upgraded-to-5-1-2-parsing-of-flex-projects-to-t ...
-
nginx配置-为没有后缀的文件(实际上是有html文件)以html形式打开
location ~ index.php@ { add_header content-type "text/html"; }
-
Linux命令之pwd
从今天开始,我会慢慢的把学习Linux过程中的一些命令简单的介绍一下,只是简单的介绍. 我的系统是Ubantu pwd命令 用处:查看当前所在的目录 用法:直接在终端里面输入pwd就好了 示例:
-
AngularJS实战之cookie的读取
<!DOCTYPE html> <html ng-controller="cookies_controller"> <head> <tit ...
-
Actor模式初步入门
Actor模型概念 Actor模型为并行而生,简单说是未解决高并发的一种编程思路.在Actor模型中,主角是Actor,类似一种worker,Actor彼此之间直接发送消息,不需要经过什么中介,消息是 ...
-
使用Axure RP原型设计实践02,自定义部件以及熟悉与部件相关面板
本篇体验在Axure中自定义部件,并熟悉Widget Interations and Notes面板,Widget Properties and Style面板,Widget Manager面板. 在 ...
-
JavaScript中的方法、方法引用和参数
首先,我们来看一段代码,如果觉得不甚明白的,则本文会对你有益: var player = function (e) { return (function f(m) { ...
-
request.getParameterMap()获得Map中的数据
今天使用request.getParameterMap()获得Map中的数据时,使用 Map map=request.getParameterMap(); i ...
-
Android开发日记(五)
从服务器端传递多个数据 先在服务器端设置cs文件 using Newtonsoft.Json; using Newtonsoft.Json.Linq; using System; using Syst ...