新普金娱乐网址


数学及时就是是自个儿的少女时代啊

认清性能问题

BZOJ4817 SDOI2017 相关分析

  • 十月 16, 2018
  • 数学
  • 没有评论

即是知乎上一个题材,值得一报。题目之补是“当自家拥有了还有望的眼界,更胜似一些的布局,我当都傲然的自我便如就井底之蛙。而自己又非太愿意接受自己是经营不善之。”

4821: [Sdoi2017]连带分析

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special
Judge

儿时给夸多矣智,还确实认为自己老聪明之。慢慢才发不甘平庸的心情。

Description

Frank对天文学非常感谢兴趣,他每每用望远镜看少,同时记录下其的信,比如亮度、颜色等等,进而估算出

有数的距离,半径等等。Frank不仅喜欢观察,还爱好分析观测到之多少。他常常分析两独参数之间(比如亮度和

半径)是否存在某种关系。现在Frank要分析参数X与Y之间的涉。他来n组观测数据,第i组观测数据记录了x_i和

y_i。他欲瞬间几乎种操作1
L,R:用直线拟合第L组到底R组观测数据。用xx表示这些观测数据中x的平均数,用yy

代表这些观测数据中y的平均数,即

xx=Σx_i/(R-L+1)(L<=i<=R)

yy=Σy_i/(R-L+1)(L<=i<=R)

若果直线方程是y=ax+b,那么a应当这样算:

a=(Σ(x_i-xx)(y_i-yy))/(Σ(x_i-xx)(x_i-xx))
(L<=i<=R)

公得帮忙Frank计算a。

2 L,R,S,T:

Frank发现测量数据第L组到底R组数据产生误差,对每个i满足L
<= i <= R,x_i需要加上S,y_i需要加上T。

3 L,R,S,T:

Frank发现第L组到第R组数要修改,对于每个i满足L
<= i <= R,x_i需要修改为(S+i),y_i需要修改也(T+i)。

弱智与否,无非是同同龄人相比的。这无异比起生理角度似乎充满正当性,却不经意了所谓遗传和家庭环境。所以慢慢形成的思想意识是,超过大多数同龄人就深受厉害,落后于大部分口就被普通。比方说若小学奥数拿了冠军,比打高中时会举行小学奥数书,都如觉得自己非平庸得差不多。

Input

第一履行两个数n,m,表示观测数据组数和操作次数。

连接下一行n个数,第i个数是x_i。

通下去一行n个数,第i个数是y_i。

搭下去m行,表示操作,格式见题目叙述。

1<=n,m<=10^5,0<=|S|,|T|,|x_i|,|y_i|<=10^5

保1操作不见面面世分母为0的情形。

自身已用觉得好非常聪明伶俐,还是多超常同龄人的那种聪明。上小学前曾经会认大多数时不时因此汉字,会一百内的加减乘除,三年级开始模拟英语时词汇量比其他同学多一些。连老师且赞叹我明白,让自家感觉自己决定极了。后来本身成绩一直挺好,也自以为天赋过口。

Output

对每个1操作,输出一行,表示直线斜率a。

选手输出和标准输出的绝对误差不超10^-5尽管为科学。

委让自己意识及好平庸之,是小学起初中时的一样软不同寻常招生考试。那是一律所全市最好的中学的征集,我构思自己优于他人这么多,别人花了全套一学期准备,我倒是始终非常有自信,觉得十拿九稳之,我究竟那精彩。

Sample Input

3 5
1 2 3
1 2 3
1 1 3
2 2 3 -3 2
1 1 2
3 1 2 2 1
1 1 3

后来自己尚未考进。现在推断理所当然,当时却一筹莫展接受。借到电话说没有进,一下子扑在枕头上哭得稀里哗啦。忽然知道好无法不劳而获,再也不能靠在智慧轻松战胜,整整一个礼拜没有笑过。

Sample Output

1.0000000000
-1.5000000000
-0.6153846154

 

  本来我是不会见回忆就道题的。但是来诸如此类一个故事:

  开学,学科,数学课,变量的相关性。

  下课后,同学等集合在同步搞事。

  QT:“你记不记得SDOI2017 D2T3
相关分析?”

  我:“……蛤?”

  QT:“题目没有被你化简,数学书上化简了。”

  我:“……蛤?”

  QT:“拆起来式子之后有4单东西一旦保障,我弗见面(想)写。”

  我:“……蛤?”

  …………

  在机房写作业。

  QT:“不行这个数学作业太难算了,我而编程计算。”

  Anson:“你得打一波SDOI2017
相关分析。”

  QT(虚伪地):“我不会见自。”

  然而因为我已从Jesse那里蒯了一个calc.cpp,作业都勾勒了了。

  然后自便只是怀念看传说被的SDOI2017D2T3凡啊开,我是匪是忘的同等关系二都。

  然后发现果然忘得一样干二全。

  然后即使发生了下的政工。

 

  题解就是众所周知的线树。

  将架子拆起来羁押,你尽管会见赢得:

 

  图片 1

  

  上下的背后那同样段落得更化简一下。

  然后虽使维护4单东西:

  

  图片 2

  

  这个就算异常simple了咔嚓,线段树嘛。

  对于操作2,3,把前后的姿态拆一下,维护一下即便吓了。

  可以事先做codevs的 线段树练习5
思路都是差不多的。

  思维难度:高中数学。

  代码难度:MDZZ。

  PS:这道题就别再codevs交了,它没有SPJ。

图片 3图片 4

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <complex>
#include    <stack>
#define LL long long int
#define dob long double
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;

const int N = 400010;
struct Tree{
  dob x,y,xx,xy;
  Tree operator +(const Tree &t){
    return (Tree){x+t.x,y+t.y,xx+t.xx,xy+t.xy};
  }
}Tr[N*4];
int n,m,lazy_vis[N];
dob X[N/4],Y[N/4],lazy_add1[N],lazy_add2[N],lazy_set1[N],lazy_set2[N];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}

inline void build(int x,int l,int r){
  if(l==r){
    Tr[x]=(Tree){X[l],Y[l],1.0*X[l]*X[l],1.0*X[l]*Y[l]};
    return;
  }
  int mid=(l+r)>>1;
  build(ls,l,mid);build(rs,mid+1,r);
  Tr[x]=Tr[ls]+Tr[rs];
}

inline dob calc(dob l,dob r){
  return 0.5*(l+r)*(r-l+1);
}

inline dob calcpow(dob l,dob r){
  l-=1;
  dob p1=1.0*(r)*(r+1)*(2*r+1)/6.0;
  dob p2=1.0*(l)*(l+1)*(2*l+1)/6.0;
  return p1-p2;
}

inline void down(int x,int l,int r){
  int mid=(l+r)>>1,sl=mid-l+1,sr=r-mid;
  if(lazy_vis[x]){
    lazy_add1[ls]=lazy_add1[rs]=lazy_add2[ls]=lazy_add2[rs]=0;
    lazy_vis[ls]=lazy_vis[rs]=1;
    dob S=lazy_set1[x],T=lazy_set2[x];
    lazy_set1[ls]=lazy_set1[rs]=lazy_set1[x];
    lazy_set2[ls]=lazy_set2[rs]=lazy_set2[x];
    Tr[ls].xx=1.0*sl*S*S+2.0*S*calc(l,mid)+calcpow(l,mid);
    Tr[rs].xx=1.0*sr*S*S+2.0*S*calc(mid+1,r)+calcpow(mid+1,r);
    Tr[ls].xy=1.0*sl*S*T+1.0*(S+T)*calc(l,mid)+calcpow(l,mid);
    Tr[rs].xy=1.0*sr*S*T+1.0*(S+T)*calc(mid+1,r)+calcpow(mid+1,r);
    Tr[ls].x=1.0*sl*S+calc(l,mid);Tr[rs].x=1.0*sr*S+calc(mid+1,r);
    Tr[ls].y=1.0*sl*T+calc(l,mid);Tr[rs].y=1.0*sr*T+calc(mid+1,r);
    lazy_vis[x]=0;
  }
  if(lazy_add1[x] || lazy_add2[x]){
    dob S=lazy_add1[x],T=lazy_add2[x];
    lazy_add1[ls]+=S;lazy_add1[rs]+=S;
    lazy_add2[ls]+=T;lazy_add2[rs]+=T;
    Tr[ls].xx+=2.0*Tr[ls].x*S+1.0*sl*S*S;
    Tr[rs].xx+=2.0*Tr[rs].x*S+1.0*sr*S*S;
    Tr[ls].xy+=1.0*Tr[ls].x*T+1.0*Tr[ls].y*S+1.0*sl*S*T;
    Tr[rs].xy+=1.0*Tr[rs].x*T+1.0*Tr[rs].y*S+1.0*sr*S*T;
    Tr[ls].x+=1.0*sl*S;Tr[rs].x+=1.0*sr*S;
    Tr[ls].y+=1.0*sl*T;Tr[rs].y+=1.0*sr*T;
    lazy_add1[x]=lazy_add2[x]=0;
  }
}

inline Tree query_1(int x,int l,int r,int xl,int xr){
  if(xl<=l && r<=xr)return Tr[x];
  down(x,l,r);int mid=(l+r)>>1;
  if(xr<=mid)return query_1(ls,l,mid,xl,xr);
  else if(xl>mid)return query_1(rs,mid+1,r,xl,xr);
  return query_1(ls,l,mid,xl,mid)+query_1(rs,mid+1,r,mid+1,xr);
}

inline void update_2(int x,int l,int r,int xl,int xr,dob S,dob T){
  if(xl<=l && r<=xr){
    lazy_add1[x]+=S;lazy_add2[x]+=T;
    Tr[x].xx+=2.0*Tr[x].x*S+1.0*(r-l+1)*S*S;
    Tr[x].xy+=1.0*Tr[x].x*T+1.0*Tr[x].y*S+1.0*(r-l+1)*S*T;
    Tr[x].x+=1.0*(r-l+1)*S;Tr[x].y+=1.0*(r-l+1)*T;
    return;
  }
  down(x,l,r);int mid=(l+r)>>1;
  if(xr<=mid)update_2(ls,l,mid,xl,xr,S,T);
  else if(xl>mid)update_2(rs,mid+1,r,xl,xr,S,T);
  else update_2(ls,l,mid,xl,mid,S,T),update_2(rs,mid+1,r,mid+1,xr,S,T);
  Tr[x]=Tr[ls]+Tr[rs];
}

inline void update_3(int x,int l,int r,int xl,int xr,dob S,dob T){
  if(xl<=l && r<=xr){
    lazy_add1[x]=lazy_add2[x]=0;
    lazy_vis[x]=1;lazy_set1[x]=S;lazy_set2[x]=T;
    Tr[x].xx=1.0*(r-l+1)*S*S+2.0*S*calc(1.0*l,1.0*r)+calcpow(1.0*l,1.0*r);
    Tr[x].xy=1.0*(r-l+1)*S*T+1.0*(S+T)*calc(l,r)+calcpow(l,r);
    Tr[x].x=1.0*(r-l+1)*S+calc(l,r);Tr[x].y=1.0*(r-l+1)*T+calc(l,r);
    return;
  }
  down(x,l,r);int mid=(l+r)>>1;
  if(xr<=mid)update_3(ls,l,mid,xl,xr,S,T);
  else if(xl>mid)update_3(rs,mid+1,r,xl,xr,S,T);
  else update_3(ls,l,mid,xl,mid,S,T),update_3(rs,mid+1,r,mid+1,xr,S,T);
  Tr[x]=Tr[ls]+Tr[rs];
}   

int main()
{
  /*freopen(".in","r",stdin);
    freopen(".out","w",stdout);*/
  n=gi();m=gi();
  for(int i=1;i<=n;++i)X[i]=gi();
  for(int i=1;i<=n;++i)Y[i]=gi();
  build(1,1,n);
  for(int i=1;i<=m;++i){
    int type=gi();
    if(type==1){
      int l=gi(),r=gi();
      Tree ans=query_1(1,1,n,l,r);
      dob fz=ans.xy-ans.x*ans.y/(r-l+1);
      dob fm=ans.xx-ans.x*ans.x/(r-l+1);
      printf("%.10Lf\n",fz/fm);
    }
    if(type==2){
      int l=gi(),r=gi(),S=gi(),T=gi();
      update_2(1,1,n,l,r,1.0*S,1.0*T);
    }
    if(type==3){
      int l=gi(),r=gi(),S=gi(),T=gi();
      update_3(1,1,n,l,r,1.0*S,1.0*T);
    }
  }

  /*fclose(stdin);
    fclose(stdout);*/
  return 0;
}

系分析

 

如今想来,小时候会加减乘除,是因家人提前让过自己。有一部分词汇量,是为提前上过暑假补习班。认得很多字,是坐盯在电视字幕看了有限年电视…这些领先
从不源于天赋,而是提前量。所以若跨同龄人的艺术,或者说证明自己的莫平庸,多爱,提前做,花时间,把从麻将的生命力用来坐单词,就够用了。

起来模拟奥数的当儿,发现人家比自己来更多的算法。开始效仿化学竞赛的上,发现自己元素周期表还忘记。后来读了文科,发现自己连十三透过都说不统。

或许给您以为,啊我真的平庸,我真的没因此,我怎么差别人这样多。其实以发生什么为,不懂得就仿照,没念了就读。所谓人及丁里面智商的反差真是,但更多时候是投机时从没用够。所谓大多数口大力的程度,尚不足以埋怨天赋,我是肯定的。

自这里的座谈排除了众客观因素,比方家庭,比方环境。但多数时候的弱智,无非是极力不够,然后就是天赋不足。

立在原基础及的自信,是雅虚无的。我得了争的完成,是为自然了口,这样的调调,也是死凶险的。因为若无法印证,也无力回天证伪。我今天承认自己是单可怜平庸之丁,除了爱吃能睡,偶尔写点文章勉强算是特长,就是个老一般的人数,丢到人流里除矮点没别的特色。

不过建立于使劲基础及之进步,却是真正而谢的。现在本身明白自己从未是天赋,曾经于其他人做得好有的的,是以自己付出了不遗余力,而若受祥和连续开拓进取,无非也是赖继续努力。用时与活力,日积月累地错一个美好的好,是基本上有成就感的行。

自己当不可知免俗地会习惯以及同龄人比较,反省自己之所为。但自啊不时喜欢,自己于之前发生了提高,比方说自家毕竟开始敢用英语和丁对话了,比方说自开看得掌握一些满数学符号的论文了,这些以大部分以及专业的同龄人眼中,无比容易的事,我渐渐好了。我死开心,因为马上让自身是同一种植进步。

而在同龄人的维度上,应该说,我是一个后进生,在不停地做别人好的行。但人生是团结的,路那么长,总要时时刻刻跟他人比,然后自暴自弃一普整个说自己平庸,然后还被自己从鸡血。太辛苦了。

于拼命,在腾飞。这比由已误以为自己不过智慧,让自身觉着踏实得几近。我也许走得放缓了点,落后那些天才多,甚至可能一辈子且心有余而力不足追及。

唯独我为什么一定用追及呢。

选一稍微段原题里,我无比欣赏的黄不会的回答(如发侵权马上去):

”我之头像是野原广志,就是蛮野原新之助的父。他是东京之一个上班族,身上发生三十年之房贷要还,脚特别烦人,养活一个妻,一儿一女和一条狗。每天也加班堵,最酷之希就是是每晚回家能喝一样杯子冰镇的啤酒,要那种小苦,倒出会冒出无数气泡的啤酒。他尚好色,喜欢看走过经过的玉女,喜欢私藏写真集,还会暗中把妈妈桑给的片子藏起来,但是他那个轻他的内。他吧特别易他的生活。

上班族野原广志,虽然发生三十年之房贷,永远都没空不了事的加班,上级领导不停歇的苛责,他当即一辈子也老不便发啊坏财富;但是他呢发出一个很容易他的婆姨,有一个温馨美满的家,有下班回家的冰镇啤酒。他则从都是一个普通人,一个弱智的口,但是他向都不曾放弃了针对性活的怜爱和追求,没有弃了对家中之权责。而这般的活,其实为就算是自家者普通人,所能体悟的,最精彩的生活了。“

每一样步都赢得于好眼前,每一样步都以向阳前方,这虽那个贵重了,毕竟“我无比平庸”,是大部分人口放弃努力的借口。

生和好之想及活,在扎实往前移动,还会顺便开心地活着。

立刻就算好值得大多数人口眼热了。

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图