Hướng dẫn giải của [HueICT 2026] Cập nhật mảng

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Editorial - Cập nhật mảng

Ý tưởng

Duyệt truy vấn từ đầu sẽ rất chậm vì truy vấn loại ~1~ có thể tác động lên cả đoạn ~[l, N]~.

Ta đổi góc nhìn: duyệt truy vấn từ cuối về đầu.

Một truy vấn ~2\ p\ y~ cộng ~y~ vào ~a_p~.
Sau thời điểm đó, giá trị vừa cộng còn bị nhân tiếp bởi mọi truy vấn ~1\ l\ x~ phía sau sao cho ~l \le p~.

Vì vậy, khi duyệt ngược:

nếu gặp truy vấn loại ~1~, ta ghi nhận rằng mọi vị trí từ ~l~ đến ~N~ sẽ có thêm một hệ số nhân ~x~
nếu gặp truy vấn loại ~2~, ta cộng vào đáp án tại vị trí ~p~ lượng ~y \times mul(p)~, trong đó ~mul(p)~ là tích всех hệ số nhân hiện đang tác động lên ~p~

Cuối cùng, mỗi phần tử gốc ~a_i~ cũng đóng góp ~a_i \times mul(i)~.

Dữ liệu cấu trúc

Ta cần:

cập nhật nhân trên suffix ~[l, N]~
truy vấn tích nhân tại một điểm ~p~

Có thể dùng Fenwick Tree theo phép nhân modulo.

Độ phức tạp

Mỗi truy vấn: ~O(\log N)~
Mỗi phần tử cuối cùng: ~O(\log N)~

Tổng: ~O((N + Q)\log N)~

Code C++ tham khảo

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

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
const int MOD = (int)1e9 + 7;

struct FenwickTree {
    vector<int> bit;
    int n;

    FenwickTree(int _n = 0) {
        n = _n;
        if (n > 0) bit.assign(n + 1, 1);
    }

    void update(int x, int d) {
        for (; x <= n; x += x & -x) bit[x] = 1LL * bit[x] * d % MOD;
    }

    int get(int x) const {
        int res = 1;
        for (; x >= 1; x &= x - 1) res = 1LL * res * bit[x] % MOD;
        return res;
    }
};

struct Query {
    int type, pos, val;
    void input() {
        scanf("%d%d%d", &type, &pos, &val);
        val = (val % MOD + MOD) % MOD;
    }
};

const int MAX = 1000100;
int a[MAX], n, q, res[MAX];
Query queries[MAX];

int main() {
    scanf("%d%d", &n, &q);
    FOR(i, 1, n) {
        scanf("%d", &a[i]);
        a[i] = (a[i] % MOD + MOD) % MOD;
    }
    FOR(i, 1, q) queries[i].input();

    FenwickTree bit(n);

    FORD(i, q, 1) {
        if (queries[i].type == 1) bit.update(queries[i].pos, queries[i].val);
        else {
            int p = queries[i].pos;
            res[p] = (res[p] + 1LL * queries[i].val * bit.get(p)) % MOD;
        }
    }

    FOR(i, 1, n) {
        res[i] = (res[i] + 1LL * a[i] * bit.get(i)) % MOD;
    }

    FOR(i, 1, n) printf("%d ", res[i]);
    printf("\n");
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.