题目描述

写一个数据结构，维护两个序列 $\{x _ i\}$ 和 $\{y _ i\}$，支持

• 给定 $L, R$，求 $\begin {aligned} \frac {\sum _ {i = L} ^ R (x _ i - \overline x) (y _ i - \overline y)} {\sum _ {i = L} ^ R (x _ i - \overline x) ^ 2} \end {aligned}$
• 给定 $L, R, S, T$，对 $L \leq i \leq R$ 的 $i$，让 $x _ i$ 加上 $S$，$y _ i$ 加上 $T$
• 给定 $L, R, S, T$，对 $L \leq i \leq R$ 的 $i$，将 $x _ i$ 变成 $S + i$，$y _ i$ 变成 $T + i$

算法1

(线段树) $O(n \log n)$

裸的线段树板子题竟没有题解！

先推式子，看让求的那个东西，

$$ \frac {\sum _ {i = L} ^ R (x _ i - \overline x) (y _ i - \overline y)} {\sum _ {i = L} ^ R (x _ i - \overline x) ^ 2} $$

分子：

$$ \begin {aligned} & \sum _ {i = L} ^ R (x _ i - \overline x) (y _ i - \overline y) \\\ = & \bigg[\sum _ {i = L} ^ R x _ i (y _ i - \overline y)\bigg] - \bigg[\overline x \sum _ {i = L} ^ R (y _ i - \overline y)\bigg] \\\ \end {aligned} $$

注意到右边 $ \begin {aligned} \sum _ {i = L} ^ R (y _ i - \overline y) = 0 \end {aligned} $

因此分子可化为

$$ \begin {aligned} & \sum _ {i = L} ^ R x _ i (y _ i - \overline y) \\\ = & \bigg(\sum _ {i = L} ^ R x _ i y _ i \bigg) - \bigg(\overline y \sum _ {i = L} ^ R x _ i \bigg) \\\ = & \bigg(\sum _ {i = L} ^ R x _ i y _ i \bigg) - \frac {\big(\sum _ {i = L} ^ R y _ i \big) \big(\sum _ {i = L} ^ R x _ i \big)} {R - L + 1} \\\ \end {aligned} $$

因此可以在线段树上维护 $ \begin {aligned} \texttt s = \sum _ {i = L} ^ R x _ i y _ i, \ \texttt{sy} = \sum _ {i = L} ^ R y _ i, \ \texttt{sx} = \sum _ {i = L} ^ R x _ i \end {aligned} $

那么上式即为 $\texttt s - \displaystyle \frac {\texttt{sy} \times \texttt{sx}} {R - L + 1}$

分母：

$$ \sum _ {i = L} ^ R (x _ i - \overline x) ^ 2 $$

关于这个东西的维护是经典操作了，秦淮岸在这篇分享{target=”_blank”}中写到了。

这里直接说做法，维护 $\texttt {vx} = \sum _ {i = L} ^ R x _ i ^ 2$，那么分母即为 $\texttt {vx} - \displaystyle \frac {\texttt{sx} ^ 2} {R - L + 1}$

至于区间加、区间改，也都是线段树的常规操作，实现时注意操作顺序等细节即可。具体可见代码及注释。

时间复杂度

线段树板子，$O(n \log n)$

C++ 代码

#include <cstdio>
#include <cstring>

const int N = 100005;

int n, m;
double x[N], y[N];
struct Tree
{
    int l, r;
    double s, sx, vx, sy;             // 维护的 l ~ r 这段区间内的四个信息
    double addx, addy, samex, samey;  // 区间加具体值 & 区间改具体值
    bool add, same;                   // 区间加标记 & 区间改标记
} tr[N << 2];

// 将 a 和 b 两个节点的信息合并到 x 中
inline void update(Tree& x, const Tree a, const Tree b)
{
    x.s = a.s + b.s;
    x.sx = a.sx + b.sx;
    x.sy = a.sy + b.sy;
    x.vx = a.vx + b.vx;
}

// 通过 x 的两个子节点信息更新 x 的信息
inline void update(int x)
{
    update(tr[x], tr[x << 1], tr[x << 1 | 1]);
}

// 下传 same 标记
inline void same(Tree& t, double x, double y)
{
    // 如果该节点上有 add 标记，则应覆盖掉
    if (t.add)
    {
        t.add = false;
        t.addx = t.addy = 0;
    }
    double s = (t.r - t.l + 1.0) * (t.l + t.r) / 2;
    double ss = (t.r * (t.r + 1.0) * (2.0 * t.r + 1) - t.l * (t.l - 1.0) * (2.0 * t.l - 1)) / 6;
    t.sx = x * (t.r - t.l + 1) + s;
    t.sy = y * (t.r - t.l + 1) + s;
    t.s = x * y * (t.r - t.l + 1) + (x + y) * s + ss;
    t.vx = x * x * (t.r - t.l + 1) + 2 * x * s + ss;
    t.samex = x, t.samey = y;
    t.same = true;
}

// 下传 add 标记
inline void add(Tree& t, double x, double y)
{
    t.s += x * t.sy + y * t.sx + x * y * (t.r - t.l + 1);
    t.vx += 2 * x * t.sx + x * x * (t.r - t.l + 1);
    t.sx += x * (t.r - t.l + 1);
    t.sy += y * (t.r - t.l + 1);
    if (t.same) t.samex += x, t.samey += y; // 如果本来有 same 标记，在 add 的时候等价于直接把 same 的值加上 add 的值
    else // 否则处理 add 标记
    {
        t.addx += x, t.addy += y;
        t.add = true;
    }
}

// 下传节点 u 的所有标记
inline void pushdown(int u)
{
    static double x, y;
    if (tr[u].same)
    {
        x = tr[u].samex, y = tr[u].samey;
        same(tr[u << 1], x, y);
        same(tr[u << 1 | 1], x, y);
        tr[u].same = false;
    }
    if (tr[u].add)
    {
        x = tr[u].addx, y = tr[u].addy;
        add(tr[u << 1], x, y);
        add(tr[u << 1 | 1], x, y);
        tr[u].addx = tr[u].addy = 0;
        tr[u].add = false;
    }
}

// 建线段树
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r)
    {
        tr[u].sx = x[r];
        tr[u].sy = y[r];
        tr[u].s = x[r] * y[r];
        tr[u].vx = x[r] * x[r];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    update(u);
}

// 处理询问
Tree query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    if (mid < l) return query(u << 1 | 1, l, r);
    Tree res;
    update(res, query(u << 1, l, r), query(u << 1 | 1, l, r));
    return res;
}

// 执行题目中修改操作 2
void change1(int u, int l, int r, double s, double t)
{
    if (tr[u].l >= l && tr[u].r <= r) add(tr[u], s, t);
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) change1(u << 1, l, r, s, t);
        if (mid < r) change1(u << 1 | 1, l, r, s, t);
        update(u);
    }
}

// 执行题目中修改操作 3
void change2(int u, int l, int r, double s, double t)
{
    if (tr[u].l >= l && tr[u].r <= r) same(tr[u], s, t);
    else
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) change2(u << 1, l, r, s, t);
        if (mid < r) change2(u << 1 | 1, l, r, s, t);
        update(u);
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    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);
    int c, l, r;
    double s, t;
    while (m--)
    {
        scanf("%d%d%d", &c, &l, &r);
        if (c == 1)
        {
            Tree res = query(1, l, r);
            r -= l - 1; // 直接用 r 存区间 l ~ r 的长度，方便计算答案
            printf("%.10lf\n", (res.s * r - res.sx * res.sy) / (res.vx * r - res.sx * res.sx));
        }
        else if (c == 2)
        {
            scanf("%lf%lf", &s, &t);
            change1(1, l, r, s, t);
        }
        else
        {
            scanf("%lf%lf", &s, &t);
            change2(1, l, r, s, t);
        }
    }
    return 0;
}

$$ $$