相關(guān)分析

Time Limit: 10 Sec??Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

　　Frank對(duì)天文學(xué)非常感興趣，他經(jīng)常用望遠(yuǎn)鏡看星星，同時(shí)記錄下它們的信息，比如亮度、顏色等等，進(jìn)而估算出星星的距離，半徑等等。 　　Frank不僅喜歡觀測(cè)，還喜歡分析觀測(cè)到的數(shù)據(jù)。他經(jīng)常分析兩個(gè)參數(shù)之間（比如亮度和半徑）是否存在某種關(guān)系。 　　現(xiàn)在Frank要分析參數(shù)X與Y之間的關(guān)系。 　　他有n組觀測(cè)數(shù)據(jù)，第i組觀測(cè)數(shù)據(jù)記錄了x_i和y_i。 　　他需要一下幾種操作 　　1 L,R：用直線擬合第L組到底R(shí)組觀測(cè)數(shù)據(jù)。 　　　　用xx表示這些觀測(cè)數(shù)據(jù)中x的平均數(shù)，用yy表示這些觀測(cè)數(shù)據(jù)中y的平均數(shù)，即 　　　　　　xx=Σx_i/(R-L+1)(L<=i<=R) 　　　　　　yy=Σy_i/(R-L+1)(L<=i<=R) 　　　　如果直線方程是y=ax+b，那么a應(yīng)當(dāng)這樣計(jì)算： 　　　　　　a=(Σ(x_i-xx)(y_i-yy))/(Σ(x_i-xx)(x_i-xx)) (L<=i<=R) 　　　　你需要幫助Frank計(jì)算a。 　　2 L,R,S,T： 　　　　Frank發(fā)現(xiàn)測(cè)量數(shù)據(jù)第L組到底R(shí)組數(shù)據(jù)有誤差，對(duì)每個(gè)i滿足L <= i <= R，x_i需要加上S，y_i需要加上T。 　　3 L,R,S,T： 　　　　Frank發(fā)現(xiàn)第L組到第R組數(shù)據(jù)需要修改，對(duì)于每個(gè)i滿足L <= i <= R，x_i需要修改為(S+i)，y_i需要修改為(T+i)。

Input

　　第一行兩個(gè)數(shù)n,m，表示觀測(cè)數(shù)據(jù)組數(shù)和操作次數(shù)。 　　接下來(lái)一行n個(gè)數(shù)，第i個(gè)數(shù)是x_i。 　　接下來(lái)一行n個(gè)數(shù)，第i個(gè)數(shù)是y_i。 　　接下來(lái)m行，表示操作，格式見題目描述。 　　保證1操作不會(huì)出現(xiàn)分母為0的情況。

Output

　　對(duì)于每個(gè)1操作，輸出一行，表示直線斜率a。 　　選手輸出與標(biāo)準(zhǔn)輸出的絕對(duì)誤差不超過(guò)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

HINT

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

Main idea

　　維護(hù)一個(gè)線性回歸方程，需要支持區(qū)間加，區(qū)間覆蓋等差數(shù)列。

Solution

　　我們先化一個(gè)式子：

　　然后就只要運(yùn)用線段樹維護(hù) Σx Σy Σxx Σxy 就可以了。

　　每一個(gè)具體怎么維護(hù)的話，就是把式子列出來(lái)，暴力展開一下看一下其中的關(guān)聯(lián)即可，并不難（BearChild懶得寫啦！）。

Code

1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 using namespace std; 9 typedef long long s64; 10 11 const int ONE = 200005; 12 13 int n,m,P; 14 int L,R,S,T; 15 double Sumsq[ONE]; 16 double Vx[ONE],Vy[ONE]; 17 18 struct power 19 { 20 double sumx,sumy,sumxx,sumxy; 21 double addx,addy; 22 double covx,covy; 23 bool cov; 24 }Node[ONE*4]; 25 26 struct ans 27 { 28 double x,y,xx,xy; 29 }res; 30 31 inline int get() 32 { 33 int res=1,Q=1; char c; 34 while( (c=getchar())<48 || c>57) 35 if(c=='-')Q=-1; 36 if(Q) res=c-48; 37 while((c=getchar())>=48 && c<=57) 38 res=res*10+c-48; 39 return res*Q; 40 } 41 42 void Covers(int i,int l,int r,double S,double T) 43 { 44 if(l > r) return; 45 double len = r-l+1; double sum = (l+r)*len/2; 46 Node[i].addx = Node[i].addy = 0; 47 Node[i].covx = S; Node[i].covy = T; 48 Node[i].cov = 1; 49 Node[i].sumxx = S*S*len + sum*S + sum*S + Sumsq[r] - Sumsq[l-1]; 50 Node[i].sumxy = S*T*len + sum*S + sum*T + Sumsq[r] - Sumsq[l-1]; 51 Node[i].sumx = (S+l + S+r)*len / 2; 52 Node[i].sumy = (T+l + T+r)*len / 2; 53 } 54 55 void PC(int i,int l,int r) 56 { 57 if(Node[i].cov) 58 { 59 int mid = l+r>>1; 60 Covers(i<<1,l,mid, Node[i].covx,Node[i].covy); 61 Covers(i<<1|1,mid+1,r, Node[i].covx,Node[i].covy); 62 Node[i].cov = 0; 63 } 64 } 65 66 void Update(int i,int l,int r,double S,double T) 67 { 68 if(l > r) return; 69 PC(i,l,r); 70 double len = r-l+1; 71 Node[i].addx += S; Node[i].addy += T; 72 Node[i].sumxx += 2*S*Node[i].sumx + S*S*len; 73 Node[i].sumxy += S*Node[i].sumy + T*Node[i].sumx + S*T*len; 74 Node[i].sumx += S*len; Node[i].sumy += T*len; 75 } 76 77 void PU(int i,int l,int r) 78 { 79 if(Node[i].addx || Node[i].addy) 80 { 81 int mid = l+r>>1; 82 Update(i<<1,l,mid, Node[i].addx,Node[i].addy); 83 Update(i<<1|1,mid+1,r, Node[i].addx,Node[i].addy); 84 Node[i].addx = Node[i].addy = 0; 85 } 86 } 87 88 void pushdown(int i,int l,int r) 89 { 90 PU(i,l,r); PC(i,l,r); 91 } 92 93 void Renew(int i) 94 { 95 int a = i<<1, b = i<<1|1; 96 Node[i].sumx = Node[a].sumx + Node[b].sumx; 97 Node[i].sumy = Node[a].sumy + Node[b].sumy; 98 Node[i].sumxx = Node[a].sumxx + Node[b].sumxx; 99 Node[i].sumxy = Node[a].sumxy + Node[b].sumxy; 100 } 101 102 void Build(int i,int l,int r) 103 { 104 if(l==r) 105 { 106 Node[i].sumx = Vx[l]; 107 Node[i].sumy = Vy[l]; 108 Node[i].sumxx = (double)Vx[l] * Vx[l]; 109 Node[i].sumxy = (double)Vx[l] * Vy[l]; 110 return; 111 } 112 int mid = l+r>>1; 113 Build(i<<1,l,mid); Build(i<<1|1,mid+1,r); 114 Renew(i); 115 } 116 117 void Cov(int i,int l,int r,int L,int R,double S,double T) 118 { 119 if(L<=l && r<=R) 120 { 121 Covers(i,l,r,S,T); 122 return; 123 } 124 125 pushdown(i,l,r); 126 int mid = l+r>>1; 127 if(L<=mid) Cov(i<<1,l,mid,L,R,S,T); 128 if(mid+1<=R) Cov(i<<1|1,mid+1,r,L,R,S,T); 129 Renew(i); 130 } 131 132 void Add(int i,int l,int r,int L,int R,double S,double T) 133 { 134 if(L<=l && r<=R) 135 { 136 Update(i,l,r,S,T); 137 return; 138 } 139 140 pushdown(i,l,r); 141 int mid = l+r>>1; 142 if(L<=mid) Add(i<<1,l,mid,L,R,S,T); 143 if(mid+1<=R) Add(i<<1|1,mid+1,r,L,R,S,T); 144 Renew(i); 145 } 146 147 void Query(int i,int l,int r,int L,int R) 148 { 149 if(L<=l && r<=R) 150 { 151 res.x += Node[i].sumx; res.y += Node[i].sumy; 152 res.xx += Node[i].sumxx; res.xy += Node[i].sumxy; 153 return; 154 } 155 156 pushdown(i,l,r); 157 int mid = l+r>>1; 158 if(L<=mid) Query(i<<1,l,mid,L,R); 159 if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R); 160 } 161 162 int main() 163 { 164 for(int i=1;i<=ONE-1;i++) Sumsq[i] = Sumsq[i-1] + (double)i*i; 165 166 n=get(); m=get(); 167 for(int i=1;i<=n;i++) Vx[i]=get(); 168 for(int i=1;i<=n;i++) Vy[i]=get(); 169 Build(1,1,n); 170 171 while(m--) 172 { 173 P = get(); L = get(); R = get(); 174 if(P == 1) 175 { 176 res.x = res.y = res.xx = res.xy = 0; 177 Query(1,1,n,L,R); 178 double len = R-L+1; 179 double Avex = res.x / len; 180 double Avey = res.y / len; 181 printf("%.6lf\n", (res.xy - len * Avex * Avey) / (res.xx - len*Avex*Avex)); 182 } 183 else 184 { 185 S = get(); T = get(); 186 if(P == 2) Add(1,1,n, L,R,S,T); 187 else Cov(1,1,n, L,R,S,T); 188 } 189 } 190 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/BearChild/p/6711245.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ4821】【SDOI2017】相关分析 [线段树]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。