A simple Blog for wyx I've been down the bottle hoping.
4821: [Sdoi2017]相关分析 线段树
发表于: | 分类: Oi | 评论:0 | 阅读:53

无脑线段树但是打起来非常闹听系列

$\hat{a}=\frac {\sum_{i=L}^R(x_i-\overline x)(y_i-\overline y)}{\sum_{i=L}^R(x_i-\overline x)^2}=\frac {(\sum_{i=L}^Rx_iy_i)-n\overline x \overline y}{(\sum_{i=L}^Rx_i^2)-n\overline x^2}$

然后我们就可以大力维护 $x,y , xy, x^2$的和就行了

有些卡精度……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef double f2;
const int N = 1e5+5;
const int M = N << 2;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0'; ch = getchar();}
    return x*f;
}

struct seg {
    f2 sumx, sumy, sumxx, sumxy, lazy_x, lazy_y;
    int len, tag;
} tr[N<<2];

f2 x[N], y[N];
int n, m, opt, dx, dy;

inline void updata(int k) {
    tr[k].sumx = tr[k<<1].sumx + tr[k<<1|1].sumx;
    tr[k].sumy = tr[k<<1].sumy + tr[k<<1|1].sumy;
    tr[k].sumxx = tr[k<<1].sumxx + tr[k<<1|1].sumxx;
    tr[k].sumxy = tr[k<<1].sumxy + tr[k<<1|1].sumxy;
}

void build(int k,int l,int r) {
    tr[k].len = r - l + 1;
    if(l==r) {
        tr[k].sumx = x[l], tr[k].sumy = y[l];
        tr[k].sumxy = x[l] * y[l];
        tr[k].sumxx = x[l] * x[l];
        return;
    }
    int mid = (l+r) >> 1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    updata(k);
}

f2 calc(int x) {
    return x*(x+1)*(2*x+1)/6;
}

inline void set(int k,f2 dx,f2 dy) {
    tr[k].sumxy += tr[k].sumx * dy + tr[k].sumy * dx + tr[k].len * dx * dy;
    tr[k].sumxx += tr[k].sumx * dx * 2 + tr[k].len * dx * dx;
    tr[k].sumx += dx * tr[k].len;
    tr[k].sumy += dy * tr[k].len;
    tr[k].lazy_x += dx, tr[k].lazy_y += dy;
}

inline void set_c(int k,int l,int r) {
    tr[k].sumx = tr[k].sumy = f2(l+r)*tr[k].len/2;
    tr[k].sumxy = tr[k].sumxx = calc(r) - calc(l-1);
    tr[k].tag = 1;
    tr[k].lazy_x = tr[k].lazy_y = 0;
}

inline void down(int k,int l,int r) {
    if(tr[k].tag) {
        tr[k].tag = 0;
        int mid = (l+r) >> 1; 
        set_c(k<<1,l,mid);
        set_c(k<<1|1,mid+1,r);
    }
    if(tr[k].lazy_x || tr[k].lazy_y) {
        set(k<<1,tr[k].lazy_x,tr[k].lazy_y);
        set(k<<1|1,tr[k].lazy_x,tr[k].lazy_y);
        tr[k].lazy_x = tr[k].lazy_y = 0;
    }
}

inline void change1(int k,int l,int r,int x,int y,int dx,int dy) {
    if(x <= l && r <= y) {
        set(k, dx, dy);
        return;
    }
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(x <= mid) change1(k<<1,l,mid,x,y,dx,dy);
    if(y > mid) change1(k<<1|1,mid+1,r,x,y,dx,dy);
    updata(k);
}

inline void change2(int k,int l,int r,int x,int y) {
    if(x <= l && r <= y) {
        set_c(k,l,r);
        return;
    }
    down(k,l,r);
    int mid = (l+r) >> 1;
    if(x <= mid) change2(k<<1,l,mid,x,y);
    if(y > mid) change2(k<<1|1,mid+1,r,x,y);
    updata(k);
}

f2 ask(int k,int l,int r,int x,int y,int opt) {
    if(x <= l && r <= y) {
        if(opt == 1) return tr[k].sumx;
        if(opt == 2) return tr[k].sumy;
        if(opt == 3) return tr[k].sumxy;
        if(opt == 4) return tr[k].sumxx;
    }
    down(k,l,r);
    int mid = (l+r) >> 1;
    f2 ans = 0;
    if(x <= mid) ans += ask(k<<1,l,mid,x,y,opt);
    if(y > mid)  ans += ask(k<<1|1,mid+1,r,x,y,opt);
    return ans;
}

int main() {
    int n = read(), m = read();
    for(int i=1;i<=n;++i) scanf("%lf", &x[i]);
    for(int i=1;i<=n;++i) scanf("%lf", &y[i]);
    build(1,1,n);
    while(m--) {
        int opt = read(), l = read(), r = read();
        if(opt == 1) {
            f2 tmp1 = ask(1,1,n,l,r,1), tmp2 = ask(1,1,n,l,r,2);
            f2 tmp3 = ask(1,1,n,l,r,3), tmp4 = ask(1,1,n,l,r,4);
            f2 p = tmp3 - tmp1 * tmp2  / (r-l+1);
            f2 q = tmp4 - tmp1 * tmp1 / (r-l+1);
            printf("%.10lf\n",p/q);
        }
        else {
            scanf("%d%d",&dx,&dy);
            if(opt == 3) change2(1,1,n,l,r);
            change1(1,1,n,l,r,dx,dy);
        }
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP