題目描述 Frank對天文學非常感興趣,他經常用望遠鏡看星星,同時記錄下它們的信息,比如亮度、顏色等等,進而估算出星星的距離,半徑等等。 Frank不僅喜歡觀測,還喜歡分析觀測到的數據。他經常分析兩個參數之間(比如亮度和半徑)是否存在某種關係。 現在Frank要分析參數XX 與YY 之間的關係。他有 ...
題目描述
Frank對天文學非常感興趣,他經常用望遠鏡看星星,同時記錄下它們的信息,比如亮度、顏色等等,進而估算出星星的距離,半徑等等。
Frank不僅喜歡觀測,還喜歡分析觀測到的數據。他經常分析兩個參數之間(比如亮度和半徑)是否存在某種關係。
現在Frank要分析參數XX 與YY 之間的關係。他有nn 組觀測數據,第ii 組觀測數據記錄了x_ixi 和y_iyi 。他需要一下幾種操作
- 1 L,RL,R :
用直線擬合第LL 組到底RR 組觀測數據。用\overline{x}x 表示這些觀測數據中xx 的平均數,用\overline{y}y 表示這些觀測數據中yy 的平均數,即
\overline{x}={1 \over R-L+1} \sum _{i=L} ^R x_ix=R−L+11∑i=LRxi
\overline{y}={1 \over R-L+1} \sum _{i=L} ^R y_iy=R−L+11∑i=LRyi
如果直線方程是y=ax+by=ax+b ,那麼a,ba,b 應當這樣計算:
a={\sum_{i=L} ^R (x_i-\overline{x})(y_i-\overline{y}) \over \sum _{i=L} ^R (x_i -\overline{x})^2}a=∑i=LR(xi−x)2∑i=LR(xi−x)(yi−y)
你需要幫助Frank計算aa 。
- 2 L,R,S,TL,R,S,T :
Frank發現測量數據第LL 組到底RR 組數據有誤差,對每個ii 滿足L \leq i \leq RL≤i≤R ,x_ixi 需要加上SS ,y_iyi 需要加上TT 。
- 3 L,R,S,TL,R,S,T :
Frank發現第LL 組到第RR 組數據需要修改,對於每個ii 滿足L \leq i \leq RL≤i≤R ,x_ixi 需要修改為(S+i)(S+i) ,y_iyi 需要修改為(T+i)(T+i)。
輸入輸出格式
輸入格式:
第一行兩個數n,mn,m ,表示觀測數據組數和操作次數。
接下來一行nn 個數,第ii 個數是x_ixi 。
接下來一行nn 個數,第ii 個數是y_iyi 。
接下來mm 行,表示操作,格式見題目描述。
輸出格式:
對於每個1操作,輸出一行,表示直線斜率aa 。選手輸出與標準輸出的絕對誤差或相對誤差不超過10^{-5}10−5 即為正確。
輸入輸出樣例
輸入樣例#1: 複製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輸出樣例#1: 複製
1.0000000000 -1.5000000000 -0.6153846154
說明
對於20%的數據 1 \leq n,m \leq 10001≤n,m≤1000
另有20%的數據,沒有3操作,且2操作中S=0S=0
另有30%的數據,沒有3操作。
對於100%的數據,1 \leq n,m \leq 10^5,0 \leq |S|,|T| \leq 10^5,0 \leq |x_i|,|y_i| \leq 10^51≤n,m≤105,0≤∣S∣,∣T∣≤105,0≤∣xi∣,∣yi∣≤105
保證1操作不會出現分母為00 的情況。
時間限制:1s
空間限制:128MB
考場上:
線段樹裸題—>100
wtf?為什麼會有類似等差數列的東西?—>70
maya..被卡精度了QWQ—>40
思路很簡單,把式子拆開,然後你就會發現只需要維護$x_i*y_i,x_i,y_i,x^2$的和
具體怎麼維護懶得打了(麻煩。)
建議看這裡的第一篇題解
https://www.luogu.org/problemnew/solution/P3707
// luogu-judger-enable-o2 #include<cstdio> #include<queue> #include<cstring> #define int long long #define ls k<<1 #define rs k<<1|1 #define INF 1e8+10 using namespace std; const int MAXN=1e6+10; //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++) inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct node { int l,r,siz; double po;//x^2 double mul;//xi*yi double sx,sy;//sigma double ax,ay;//add bool lazy;//memset node(){sx=-43800000;sy=-43800000;} }T[MAXN]; struct Ans { double sxiyi; double sxi,syi; double pox; Ans(){sxiyi=sxi=syi=pox=0;} }; Ans GetAns(int k) { Ans rt; rt.sxiyi=T[k].mul; rt.sxi=T[k].sx; rt.syi=T[k].sy; rt.pox=T[k].po; return rt; } void update(int k) { T[k].po=T[ls].po+T[rs].po; T[k].mul=T[ls].mul+T[rs].mul; T[k].sx=T[ls].sx+T[rs].sx; T[k].sy=T[ls].sy+T[rs].sy; } void Memset(int k) { T[k].sx=(T[k].siz*(T[k].l+T[k].r))>>1; T[k].sy=(T[k].siz*(T[k].l+T[k].r))>>1; T[k].mul=(T[k].r*(T[k].r+1)*(2*T[k].r+1))/6-(T[k].l*(T[k].l-1)*(2*T[k].l-1))/6; T[k].po=(T[k].r*(T[k].r+1)*(2*T[k].r+1))/6-(T[k].l*(T[k].l-1)*(2*T[k].l-1))/6; T[k].ax=T[k].ay=0; T[k].lazy=1; } void Clear(int k,int S,int TT) { T[k].po=T[k].po + 2.0*S*T[k].sx + T[k].siz*S*S; T[k].mul=T[k].mul + TT*T[k].sx + S*T[k].sy + T[k].siz*S*TT; T[k].sx=T[k].sx + T[k].siz*S; T[k].sy=T[k].sy + T[k].siz*TT; T[k].ax+=S; T[k].ay+=TT; } void pushdown(int k) { if(T[k].lazy) { Memset(ls); Memset(rs); T[k].lazy=0; return ; } int S=T[k].ax,TT=T[k].ay; Clear(ls,S,TT); Clear(rs,S,TT); T[k].ax=0; T[k].ay=0; } void Build(int ll,int rr,int k) { T[k].l=ll;T[k].r=rr; T[k].siz=rr-ll+1; if(ll==rr) { if(T[k].sx==-43800000) {T[k].sx=read();return ;} T[k].sy=read(); T[k].po=T[k].sx*T[k].sx; T[k].mul=T[k].sx*T[k].sy; return ; } int mid=ll+rr>>1; Build(ll,mid,ls); Build(mid+1,rr,rs); update(k); } Ans Query(int k,int ll,int rr) { pushdown(k); Ans rt; if(ll<=T[k].l&&T[k].r<=rr) { rt=GetAns(k); return rt; } pushdown(k); int mid=T[k].l+T[k].r>>1; if(ll<=mid) { pushdown(ls); Ans Q=Query(ls,ll,rr); rt.sxiyi+=Q.sxiyi; rt.sxi+=Q.sxi; rt.syi+=Q.syi; rt.pox+=Q.pox; } if(rr>mid) { pushdown(rs); Ans Q=Query(rs,ll,rr); rt.sxiyi+=Q.sxiyi; rt.sxi+=Q.sxi; rt.syi+=Q.syi; rt.pox+=Q.pox; } return rt; } void IntervalAdd(int k,int ll,int rr,int S,int TT) { pushdown(k); if(ll<=T[k].l&&T[k].r<=rr) { Clear(k,S,TT); return ; } pushdown(k); int mid=T[k].l+T[k].r>>1; if(ll<=mid) pushdown(ls),IntervalAdd(ls,ll,rr,S,TT); if(rr>mid) pushdown(rs),IntervalAdd(rs,ll,rr,S,TT); update(k); } void IntervalMemset(int k,int ll,int rr) { pushdown(k); if(ll<=T[k].l&&T[k].r<=rr) { Memset(k); return ; } pushdown(k); int mid=T[k].l+T[k].r>>1; if(ll<=mid) pushdown(ls),IntervalMemset(ls,ll,rr); if(rr>mid) pushdown(rs),IntervalMemset(rs,ll,rr); update(k); } main() { #ifdef WIN32 freopen("a.in","r",stdin); //freopen("c.out","w",stdout); #else #endif int N=read(),M=read(); Build(1,N,1); Build(1,N,1); while(M--) { int opt=read(); if(opt==1) { int L=read(),R=read(); Ans ans=Query(1,L,R); double xba=(double)ans.sxi/(double)(R-L+1); double yba=(double)ans.syi/(double)(R-L+1); double up=ans.sxiyi-(double)yba*ans.sxi-(double)xba*ans.syi + (double)xba*yba*(R-L+1); double down=ans.pox - (double)2.0*xba*ans.sxi + (double)xba*xba*(R-L+1); printf("%.10lf\n",up/down); } else if(opt==2) { int L=read(),R=read(),S=read(),TT=read(); IntervalAdd(1,L,R,S,TT); } else if(opt==3) { int L=read(),R=read(),S=read(),TT=read(); IntervalMemset(1,L,R); IntervalAdd(1,L,R,S,TT); } } return 0; }稍微整理了一下
#include<cstdio> #include<queue> #include<cstring> #define int long long #define ls k<<1 #define rs k<<1|1 #define INF 1e8+10 using namespace std; const int MAXN=1e6+10; //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++) inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct node { int l,r,siz; double po;//x^2 double mul;//xi*yi double sx,sy;//sigma double ax,ay;//add bool lazy;//memset node(){sx=-43800000;sy=-43800000;} }T[MAXN]; struct Ans { double sxiyi; double sxi,syi; double pox; Ans(){sxiyi=sxi=syi=pox=0;} }; Ans GetAns(int k) { Ans rt; rt.sxiyi=T[k].mul; rt.sxi=T[k].sx; rt.syi=T[k].sy; rt.pox=T[k].po; return rt; } void update(int k) { T[k].po=T[ls].po+T[rs].po; T[k].mul=T[ls].mul+T[rs].mul; T[k].sx=T[ls].sx+T[rs].sx; T[k].sy=T[ls].sy+T[rs].sy; } void pushdown(int k) { if(T[k].lazy) { T[ls].sx=(T[ls].siz*(T[ls].l+T[ls].r))>>1; T[ls].sy=(T[ls].siz*(T[ls].l+T[ls].r))>>1; T[ls].mul=(T[ls].r*(T[ls].r+1)*(2*T[ls].r+1))/6-(T[ls].l*(T[ls].l-1)*(2*T[ls].l-1))/6; T[ls].po=(T[ls].r*(T[ls].r+1)*(2*T[ls].r+1))/6-(T[ls].l*(T[ls].l-1)*(2*T[ls].l-1))/6; T[ls].ax=T[ls].ay=0; T[ls].lazy=1; T[rs].sx=(T[rs].siz*(T[rs].l+T[rs].r))>>1; T[rs].sy=(T[rs].siz*(T[rs].l+T[rs].r))>>1; T[rs].mul=(T[rs].r*(T[rs].r+1)*(2*T[rs].r+1))/6-(T[rs].l*(T[rs].l-1)*(2*T[rs].l-1))/6; T[rs].po=(T[rs].r*(T[rs].r+1)*(2*T[rs].r+1))/6-(T[rs].l*(T[rs].l-1)*(2*T[rs].l-1))/6; T[rs].ax=T[rs].ay=0; T[rs].lazy=1; T[k].lazy=0; return ; } int S=T[k].ax,TT=T[k].ay; T[ls].po=T[ls].po+ 2.0*S*T[ls].sx + T[ls].siz*S*S; T[ls].mul=T[ls].mul + TT*T[ls].sx + S*T[ls].sy + T[ls].siz*S*TT; T[ls].sx=T[ls].sx + T[ls].siz*S; T[ls].sy=T[ls].sy + T[ls].siz*TT; T[ls].ax+=S; T[ls].ay+=TT; T[rs].po=T[rs].po+ 2.0*S*T[rs].sx + T[rs].siz*S*S; T[rs].mul=T[rs].mul + TT*T[rs].sx + S*T[rs].sy + T[rs].siz*S*TT; T[rs].sx=T[rs].sx + T[rs].siz*S; T[rs].sy=T[rs].sy + T[rs].siz*TT; T[rs].ax+=S; T[rs].ay+=TT; T[k].ax=0; T[k].ay=0; } void Build(int ll,int rr,int k) { T[k].l=ll;T[k].r=rr; T[k].siz=rr-ll+1; if(ll==rr) { if(T[k].sx==-43800000) {T[k].sx=read();return ;} T[k].sy=read(); T[k].po=T[k].sx*T[k].sx; T[k].mul=T[k].sx*T[k].sy; return ; } int mid=ll+rr>>1; Build(ll,mid,ls); Build(mid+1,rr,rs); update(k); } Ans Query(int k,int ll,int rr) { pushdown(k); Ans rt; if(ll<=T[k].l&&T[k].r<=rr) { rt=GetAns(k); return rt; } pushdown(k); int mid=T[k].l+T[k].r>>1; if(ll<=mid) { pushdown(ls); Ans Q=Query(ls,ll,rr); rt.sxiyi+=Q.sxiyi; rt.sxi+=Q.sxi; rt.syi+=Q.syi; rt.pox+=Q.pox; } if(rr>mid) { pushdown(rs); Ans Q=Query(rs,ll,rr); rt.sxiyi+=Q.sxiyi; rt.sxi+=Q.sxi; rt.syi+=Q.syi; rt.pox+=Q.pox; } return rt; } void IntervalAdd(int k,int ll,int rr,int S,int TT) { pushdown(k); if(ll<=T[k].l&&T[k].r<=rr) { T[k].po=T[k].po + 2.0*S*T[k].sx + T[k].siz*S*S; T[k].mul=T[k].mul + TT*T[k].sx + S*T[k].sy + T[k].siz*S*TT; T[k].sx=T[k].sx + T[k].siz*S; T[k].sy=T[k].sy + T[k].siz*TT; T[k].ax+=S; T[k].ay+=TT; return ; } pushdown(k); int mid=T[k].l+T[k].r>>1; if(ll<=mid) pushdown(ls),IntervalAdd(ls,ll,rr,S,TT); if(rr>mid) pushdown(rs),IntervalAdd(rs,ll,rr,S,TT); update(k); } void IntervalMemset(int k,int ll,int rr) { pushdown(k); if(ll<=T[k].l&&T[k].r<=rr) { T[k].sx=(T[k].siz*(T[k].l+T[k].r))>>1; T[k].sy=(T[k].siz*(T[k].l+T[k].r))>>1; T[k].mul=(T[k].r*(T[k].r+1)*(2*T[k].r+1))/6-(T[k].l*(T[k].l-1)*(2*T[k].l-1))/6; T[k].po=(T[k].r*(T[k].r+1)*(2*T[k].r+1))/6-(T[k].l*(T[k].l-1)*(2*T[k].l-1))/6; T[k].ax=T[k].ay=0; T[k].lazy=1; return ; } pushdown(k); int mid=T[k].l+T[k].r>>1; if(ll<=mid) pushdown(ls),IntervalMemset(ls,ll,rr); if(rr>mid) pushdown(rs),IntervalMemset(rs,ll,rr); update(k); } main() { #ifdef WIN32 freopen("a.in","r