[OpenJudge] 平方和
2024-10-09 17:30:19
平方和
总时间限制: 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 ;
}
最新文章
- Scrapy:为spider指定pipeline
- SQL Server 2012 联机丛书离线安装
- django rest framework 的url标签的问题
- SUSE Linux下新建Weblogic 10.3非admin服务
- LinuxC 文件与目录 打印文件操作错误信息
- ACM俱乐部 字符串
- jQuery遍历DOM
- codeforces C. Painting Fence
- Android ScrollView
- Ubuntu 软件 安装 下载 及更新
- 转贴---Performance Counter(包含最全的Windows计数器解释)
- Objc将数据写入iOS真机的plist文件中
- @Scheduled cron表达式
- Grunt 一个专为JavaScript提供的构建工具
- 使用Kazoo操作ZooKeeper服务治理
- mysql之统一刷表
- 生产redis client 连接无法释放
- 约数 求反素数bzoj1053 bzoj1257
- ZooKeeper典型应用场景:分布式锁
- ERROR 1153 (08S01): Got a packet bigger than &#39;max_allowed_packet&#39; bytes怎么处理