AC日记——方差 洛谷 P1471
2024-08-26 21:01:26
思路:
线段树;
代码:
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
struct TreeNodeType {
int l,r,mid,size;
double sum,sum2,flag;
inline void updata(double x)
{
flag+=x;
sum2+=sum*x*+size*x*x;
sum+=x*size;
}
};
struct TreeNodeType tree[maxn<<];
int n,m;
double X,Sum,Sum2;
inline void in(int &now)
{
int if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
}
void build(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r,tree[now].size=r-l+;
if(l==r)
{
scanf("%lf",&tree[now].sum);
tree[now].sum2=tree[now].sum*tree[now].sum;
return;
}
tree[now].mid=l+r>>;
build(now<<,l,tree[now].mid);
build(now<<|,tree[now].mid+,r);
tree[now].sum=tree[now<<].sum+tree[now<<|].sum;
tree[now].sum2=tree[now<<].sum2+tree[now<<|].sum2;
}
inline void pushdown(int now)
{
tree[now<<].updata(tree[now].flag);
tree[now<<|].updata(tree[now].flag);
tree[now].flag=;
}
void operation1(int now,int l,int r)
{
if(tree[now].l>=l&&tree[now].r<=r)
{
tree[now].updata(X);
return;
}
if(tree[now].flag) pushdown(now);
if(l<=tree[now].mid) operation1(now<<,l,r);
if(r>tree[now].mid) operation1(now<<|,l,r);
tree[now].sum=tree[now<<].sum+tree[now<<|].sum;
tree[now].sum2=tree[now<<].sum2+tree[now<<|].sum2;
}
void operation2(int now,int l,int r)
{
if(tree[now].l>=l&&tree[now].r<=r)
{
Sum+=tree[now].sum;
Sum2+=tree[now].sum2;
return;
}
if(tree[now].flag) pushdown(now);
if(l<=tree[now].mid) operation2(now<<,l,r);
if(r>tree[now].mid) operation2(now<<|,l,r);
}
int main()
{
in(n),in(m),build(,,n);
int op,l,r;
while(m--)
{
in(op),in(l),in(r);
if(op==) scanf("%lf",&X),operation1(,l,r);
if(op==) Sum=,operation2(,l,r),printf("%.4lf\n",Sum/(r-l+));
if(op==)
{
Sum=,Sum2=;
operation2(,l,r);
X=Sum/(r-l+);
printf("%.4lf\n",(Sum2-Sum*X*+(r-l+)*X*X)/(r-l+));
}
}
return ;
}
最新文章
- python学习 第一天
- 2015.05.12:json的常用处理方式
- MyBatis学习总结(三)&mdash;&mdash;优化MyBatis配置文件中的配置
- [转]HTML5本地存储——Web SQL Database
- MTNET 自用ios网络库开源
- [整理]Code::Blocks使用遇到的问题
- 【poj1087/uva753】A Plug for UNIX(最大流)
- Linux&;shell之结构化命令
- sql server 日期处理datediff
- LB 负载均衡的层次结构(转)
- 关于【IE兼容】的都在这
- Vue + iView + vuex + vee-validate 完整项目总结
- 轻量级网络库libevent概况
- 自制操作系统Antz(7)——实现内核 (上)
- Anaconda安装及配置
- eolinker 安装时遇到的坑
- WordPress版微信小程序开发系列(二):安装使用问答
- Rpc简单入门
- 对mysql事务提交、回滚的错误理解
- python线程死锁与递归锁
热门文章
- HDU2121:Ice_cream’s world II (虚根+有向图最小生成树)
- VC使用sqlite
- POJ 3579 二分
- JVM之字节码执行引擎
- Centos下iptables常用命令
- Spring @Async开启异步任务
- 【BZOJ】4558: [JLoi2016]方
- idea如何搭建springmvc4
- 9.1docker容器 跨主机连接
- 【shell】shell中各种括号的作用()、(())、[]、[[]]、{}