[线段树]相关分析

相关分析

Time Limit: 10 Sec Memory Limit: 128 MB

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操作不会出现分母为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

HINT

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

Main idea

维护一个线性回归方程，需要支持区间加，区间覆盖等差数列。

Solution

我们先化一个式子：

然后就只要运用线段树维护 Σx Σy Σxx Σxy 就可以了。

每一个具体怎么维护的话，就是把式子列出来，暴力展开一下看一下其中的关联即可，并不难（BearChild懒得写啦！）。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 200005;

int n,m,P;
int L,R,S,T;
double Sumsq[ONE];
double Vx[ONE],Vy[ONE];

struct power
{
    double sumx,sumy,sumxx,sumxy;
    double addx,addy;
    double covx,covy;
    bool cov;
}Node[ONE*4];

struct ans
{
    double x,y,xx,xy;
}res;

inline int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Covers(int i,int l,int r,double S,double T)
{
    if(l > r) return;
    double len = r-l+1;    double sum = (l+r)*len/2;
    Node[i].addx = Node[i].addy = 0;
    Node[i].covx = S;    Node[i].covy = T;
    Node[i].cov = 1;
    Node[i].sumxx = S*S*len + sum*S + sum*S + Sumsq[r] - Sumsq[l-1];
    Node[i].sumxy = S*T*len + sum*S + sum*T + Sumsq[r] - Sumsq[l-1];
    Node[i].sumx = (S+l + S+r)*len / 2;
    Node[i].sumy = (T+l + T+r)*len / 2;
}

void PC(int i,int l,int r)
{
    if(Node[i].cov)
    {
        int mid = l+r>>1;
        Covers(i<<1,l,mid, Node[i].covx,Node[i].covy);
        Covers(i<<1|1,mid+1,r, Node[i].covx,Node[i].covy);
        Node[i].cov = 0;
    }
}

void Update(int i,int l,int r,double S,double T)
{
    if(l > r) return;
    PC(i,l,r);
    double len = r-l+1;
    Node[i].addx += S;    Node[i].addy += T;
    Node[i].sumxx += 2*S*Node[i].sumx + S*S*len;
    Node[i].sumxy += S*Node[i].sumy + T*Node[i].sumx + S*T*len;
    Node[i].sumx += S*len;    Node[i].sumy += T*len;
}

void PU(int i,int l,int r)
{
    if(Node[i].addx || Node[i].addy)
    {
        int mid = l+r>>1;
        Update(i<<1,l,mid, Node[i].addx,Node[i].addy);
        Update(i<<1|1,mid+1,r, Node[i].addx,Node[i].addy);
        Node[i].addx = Node[i].addy = 0;
    }
}

void pushdown(int i,int l,int r)
{
    PU(i,l,r);    PC(i,l,r);
}

void Renew(int i)
{
    int a = i<<1, b = i<<1|1;
    Node[i].sumx = Node[a].sumx + Node[b].sumx;
    Node[i].sumy = Node[a].sumy + Node[b].sumy;
    Node[i].sumxx = Node[a].sumxx + Node[b].sumxx;
    Node[i].sumxy = Node[a].sumxy + Node[b].sumxy;
}

void Build(int i,int l,int r)
{
    if(l==r)
    {
        Node[i].sumx = Vx[l];
        Node[i].sumy = Vy[l];
        Node[i].sumxx = (double)Vx[l] * Vx[l];
        Node[i].sumxy = (double)Vx[l] * Vy[l];
        return;
    }
    int mid = l+r>>1;
    Build(i<<1,l,mid);    Build(i<<1|1,mid+1,r);
    Renew(i);
}

void Cov(int i,int l,int r,int L,int R,double S,double T)
{
    if(L<=l && r<=R)
    {
        Covers(i,l,r,S,T);
        return;
    }

    pushdown(i,l,r);
    int mid = l+r>>1;
    if(L<=mid) Cov(i<<1,l,mid,L,R,S,T);
    if(mid+1<=R) Cov(i<<1|1,mid+1,r,L,R,S,T);
    Renew(i);
}

void Add(int i,int l,int r,int L,int R,double S,double T)
{
    if(L<=l && r<=R)
    {
        Update(i,l,r,S,T);
        return;
    }

    pushdown(i,l,r);
    int mid = l+r>>1;
    if(L<=mid) Add(i<<1,l,mid,L,R,S,T);
    if(mid+1<=R) Add(i<<1|1,mid+1,r,L,R,S,T);
    Renew(i);
}

void Query(int i,int l,int r,int L,int R)
{
    if(L<=l && r<=R)
    {
        res.x += Node[i].sumx; res.y += Node[i].sumy;
        res.xx += Node[i].sumxx; res.xy += Node[i].sumxy;
        return;
    }

    pushdown(i,l,r);
    int mid = l+r>>1;
    if(L<=mid) Query(i<<1,l,mid,L,R);
    if(mid+1<=R) Query(i<<1|1,mid+1,r,L,R);
}

int main()
{
    for(int i=1;i<=ONE-1;i++) Sumsq[i] = Sumsq[i-1] + (double)i*i;

    n=get();    m=get();
    for(int i=1;i<=n;i++)    Vx[i]=get();
    for(int i=1;i<=n;i++)    Vy[i]=get();
    Build(1,1,n);

    while(m--)
    {
        P = get();    L = get();    R = get();
        if(P == 1)
        {
            res.x = res.y = res.xx = res.xy = 0;
            Query(1,1,n,L,R);
            double len = R-L+1;
            double Avex = res.x / len;
            double Avey = res.y / len;
            printf("%.6lf\n", (res.xy - len * Avex * Avey) / (res.xx - len*Avex*Avex));
        }
        else
        {
            S = get();    T = get();
            if(P == 2) Add(1,1,n, L,R,S,T);
            else Cov(1,1,n, L,R,S,T);
        }
    }
}