洛谷P3707 [SDOI2017]相關分析(線段樹)

来源:https://www.cnblogs.com/zwfymqz/archive/2018/03/03/8502819.html
-Advertisement-
Play Games

題目描述 Frank對天文學非常感興趣,他經常用望遠鏡看星星,同時記錄下它們的信息,比如亮度、顏色等等,進而估算出星星的距離,半徑等等。 Frank不僅喜歡觀測,還喜歡分析觀測到的數據。他經常分析兩個參數之間(比如亮度和半徑)是否存在某種關係。 現在Frank要分析參數XX 與YY 之間的關係。他有 ...


題目描述

Frank對天文學非常感興趣,他經常用望遠鏡看星星,同時記錄下它們的信息,比如亮度、顏色等等,進而估算出星星的距離,半徑等等。

Frank不僅喜歡觀測,還喜歡分析觀測到的數據。他經常分析兩個參數之間(比如亮度和半徑)是否存在某種關係。

現在Frank要分析參數XX 與YY 之間的關係。他有nn 組觀測數據,第ii 組觀測數據記錄了x_ixi 和y_iyi 。他需要一下幾種操作

  • 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=RL+11i=LRxi

\overline{y}={1 \over R-L+1} \sum _{i=L} ^R y_iy=RL+11i=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(xix)2i=LR(xix)(yiy)

你需要幫助Frank計算aa 。

  • L,R,S,TL,R,S,T :

Frank發現測量數據第LL 組到底RR 組數據有誤差,對每個ii 滿足L \leq i \leq RLiR ,x_ixi 需要加上SS ,y_iyi 需要加上TT 。

  • L,R,S,TL,R,S,T :

Frank發現第LL 組到第RR 組數據需要修改,對於每個ii 滿足L \leq i \leq RLiR ,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}105 即為正確。

 

輸入輸出樣例

輸入樣例#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 10001n,m1000

另有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^51n,m105,0S,T105,0xi,yi105

保證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	   

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 解法一: 這種解法使用的是Brute Force演算法,即是暴力搜索匹配,時間複雜度較高 解法二: 這種解法的思想是計算兩個相同的字元之間的長度,好比作一個視窗在字元串上右邊框向右拉伸,若右邊框碰到視窗內已存在的字元,那麼左邊框向右拉伸到到視窗已存在字元的右邊,時間複雜度較低 github地址:htt ...
  • 研究了一些操作系統的概念,研究了I/O模式,著重研究了select、poll、epoll 的區別, ...
  • (一) 字元串 單引號、雙引號、三重引號都可以作為字元串的開始和結束,三重引號可以直接輸入多行字元串。三重引號可能一般是用來寫多行註釋。 (二) r和\ r使字元串成為原始字元串,忽略所有轉義字元。 \是轉義字元。 (三) 字元串下標和切片 (四) 字元串的in和not in (五) 改變大小寫 方 ...
  • 事先聲明,我只是java併發的新手,這篇文章也只是我閱讀《java併發編程的藝術》一書(內容主要涉及前3章)的一些總結和感悟。希望大家能多多討論,對於錯誤的地方還請指出。 0. 簡介 程式的世界是有層次分明的,每層都對外封裝細節而提供一些方式或者說介面來提供功能,甚至是約束功能來換取正確性等等。那麼 ...
  • SpringBoot中關於Mybatis使用的三個問題 轉載請註明源地址:http://www.cnblogs.com/funnyzpc/p/8495453.html 原本是要講講PostgreSQL的一些學習總結的,不巧的是最近一段時間的進度都是一些類似於加減乘除、位移、類型轉換的稍顯小兒科的一些 ...
  • istringstream用於執行C++風格的串流操作。 下麵的示例是使用一個字元串初始化istringstream類,然後再使用>>操作符來依次輸出字元串中的內容。 ...
  • 截止目前已經改造了5個類: ubuntu:通過封裝驗證碼類庫一步步安裝php的gd擴展 自定義MVC框架之工具類-分頁類的封裝 自定義MVC框架之工具類-文件上傳類 自定義MVC框架之工具類-圖像處理類 這個模型類支持以下功能: >連貫操作,js叫鏈式操作,連貫操作的函數可以打亂順序,最後一個函數必 ...
  • Go語言記憶體管理(一)記憶體分配 golang作為一種“高級語言”,也提供了自己的記憶體管理機制。這樣一方面可以簡化編碼的流程,降低因記憶體使用導致出現問題的頻率(C語言使用者尤其是初學者應該深有體會),對程式猿友好。另一方面也可以減少記憶體相關係統調用,提升性能。 先瞭解下記憶體管理大致策略: 申請一塊較大 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...