求函數

題目描述

牛可樂有 $n$ 個一次函數，第 $i$ 個函數為 $f_i(x) = k_i \times x + b_i$。

牛可樂有 $m$ 次操作，每次操作為以下二者其一：

• $1$ $i$ $k$ $b$ 將 $f_i(x)$ 修改為 $f_i(x) = k \times x + b$。
• $2$ $l$ $r$ 求 $f_r\left(f_{r-1}\left(\cdots \left(f_{l+1}\left(f_l(1)\right)\right) \cdots \right)\right)$。

牛可樂當然(bu)會做啦，他想考考你——

答案對 $10^9 + 7$ 取模。

輸入描述:

第一行，兩個正整數 $n, m$。

第二行，$n$ 個整數 $k_1, k_2, \dots, k_n$ 。

第三行，$n$ 個整數 $b_1, b_2, \dots, b_n$。

接下來 $m$ 行，每行一個操作，格式見上。

保證 $1 \leq n, m \leq 2 \times 10^5$，$0 \leq k_i, b_i < 10^9 + 7$。

輸出描述:

對于每個求值操作，輸出一行一個整數，表示答案。

示例1

輸入

2 3
1 1
1 0
1 2 114514 1919810
2 1 2
2 1 1

輸出

2148838
2

說明

初始 $f_1(x) = x + 1$，$f_2(x) = x$

修改后 $f_2(x) = 114514x + 1919810$

查詢時 $f_1(1) = 2$，$f_2(f_1(1)) = 2148838$

解題思路

??由于每個函數都是線性形式，即 $f_i(x) = k_i \times x + b_i$，我們可以展開復合函數 $f_r\left(f_{r-1}\left(\cdots \left(f_{l+1}\left(f_l(1)\right)\right) \cdots \right)\right)$，得到如下結果：

\begin{aligned}
&k_r k_{r-1} \cdots k_l \cdot 1 \\
&+ k_r k_{r-1} \cdots k_{l+1} \cdot b_l \\
&+ k_r k_{r-1} \cdots k_{l+2} \cdot b_{l+1} \\
&+ \cdots \\
&+ k_r k_{r-1} \cdots k_{l+i+1} \cdot b_{l+i} \\
&+ \cdots \\
&+ b_r \\
=& \prod_{i=l}^{r} k_i + \sum_{i=l}^{r} \left( b_i \cdot \prod_{j=i+1}^{r} k_j \right)
\end{aligned}

??由于涉及到區間查詢，因此我們考慮使用線段樹來維護上述結果。注意到整個結果可以分為兩部分：左項是 $\prod\limits_{i=l}^{r} k_i$，右項是和 $\sum\limits_{i=l}^{r} \left( b_i \cdot \prod\limits_{j=i+1}^{r} k_j \right)$ 構成。對于左項，顯然我們只需要維護區間 $[l,r]$ 內的 $k_i$ 的乘積，即 $p_{l \sim r} = \prod\limits_{i=l}^{r} k_i$。而對于右項，我們可以先考慮直接維護 $s_{l \sim r} = \sum\limits_{i=l}^{r} \left( b_i \cdot \prod\limits_{j=i+1}^{r} k_j \right)$。關鍵的問題是，當兩個區間 $[l, m]$ 與 $[m+1, r]$ 要合并成一個區間 $[l,r]$ 時，怎么得到該區間的 $s_{l \sim r}$？

??將右項繼續拆開，可以得到：

\begin{aligned}
&\sum_{i=l}^{r} \left( b_i \cdot \prod_{j=i+1}^{r} k_j \right) \\
= &\sum_{i=l}^{m} \left( b_i \cdot \prod_{j=i+1}^{r} k_j \right) + \sum_{i=m+1}^{r} \left( b_i \cdot \prod_{j=i+1}^{r} k_j \right) \\
= &\sum_{i=l}^{m} \left( b_i \cdot \prod_{j=i+1}^{m} k_j \cdot \prod_{j=m+1}^{r} k_j \right) + \sum_{i=m+1}^{r} \left( b_i \cdot \prod_{j=i+1}^{r} k_j \right) \\
= &\prod_{j=m+1}^{r} k_j \cdot \sum_{i=l}^{m} \left( b_i \cdot \prod_{j=i+1}^{m} k_j \right) + \sum_{i=m+1}^{r} \left( b_i \cdot \prod_{j=i+1}^{r} k_j \right)
\end{aligned}

??將上述表達式代入 $s_{l \sim m}$、$s_{m+1 \sim r}$ 和 $p_{m+1 \sim r}$，得到 $s_{l \sim r} = p_{m+1 \sim r} \cdot s_{l \sim m} + s_{m+1 \sim r}$。因此，我們可以利用線段樹來維護并計算區間 $[l, r]$ 內的結果。具體來說，維護每個區間的乘積 $p_{l \sim r}$ 與 $s_{l \sim r}$，并通過合并操作來得到最終結果。

??AC 代碼如下，時間復雜度為 $O(m \log{n})$：

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

typedef long long LL;

const int N = 2e5 + 5, mod = 1e9 + 7;

int a[N], b[N];
struct Node {
    int l, r, p, s;
}tr[N * 4];

Node pushup(Node l, Node r) {
    int p = 1ll * l.p * r.p % mod;
    int s = (1ll * l.s * r.p % mod + r.s) % mod;
    return {l.l, r.r, p, s};
}

void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        tr[u].p = a[l];
        tr[u].s = b[l];
    }
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
    }
}

void modify(int u, int x, int k, int b) {
    if (tr[u].l == tr[u].r) {
        tr[u].p = k;
        tr[u].s = b;
    }
    else {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, k, b);
        else modify(u << 1 | 1, x, k, b);
        tr[u] = pushup(tr[u << 1], tr[u << 1 | 1]);
    }
}

Node query(int u, int l, int r) {
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    if (l >= mid + 1) return query(u << 1 | 1, l, r);
    return pushup(query(u << 1, l, r), query(u << 1 | 1, l, r));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    build(1, 1, n);
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, k, b;
            cin >> x >> k >> b;
            modify(1, x, k, b);
        }
        else {
            int l, r;
            cin >> l >> r;
            Node t = query(1, l, r);
            cout << (t.p + t.s) % mod << '\n';
        }
    }
    
    return 0;
}

參考資料

??【題解】2020牛客寒假算法基礎集訓營第二場：https://ac.nowcoder.com/discuss/364961