Hướng dẫn giải của Biến đổi 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 làm lời giải.


Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.

Tác giả: dinhwe2612

Thuật toán

Trường hợp ~n \le 5.10^2~ và ~q \le 5.10^3~.

Với mỗi phép biến đổi có dạng (~u~, ~v~, ~k~), duyệt từ ~u~ -> ~v~ để tăng ~k~ đơn vị.

Với mỗi câu hỏi có dạng (~x~), duyệt qua ~n~ phần tử đếm xem có bao nhiêu số có giá trị là ~x~.

Độ phức tạp: ~O(m.n+n.q)~.

Trường hợp ~n \le 10^6~ và ~q \le 5~.

Ta thấy ~m.n \le 10^{10}~ quá lớn. Để tối ưu phần biến đổi, ta sử dụng kĩ thuật mảng cộng dồn.

  • Gọi ~b_i~ là độ thay đổi của phần tử thứ ~i~ sau ~m~ phép biến đổi.
  • Với mỗi phép biến đổi có dạng (~u~, ~v~, ~k~), thực hiện ~+k~ vào ~b_u~ và ~-k~ vào ~b_{v+1}~.
  • Duyệt từ ~1 \to n~ và thực hiện cộng dồn mảng ~b_{i}~.

Phần tử thứ ~i~ có giá trị sau ~m~ phép biến đổi là ~a_i+b_i~.

Độ phức tạp: ~O(m+n+n.q)~

Trường hợp ~n \le 10^6~ và ~q \le 10^6~.

Việc duyệt qua mảng ~a~ cho mỗi truy vấn là không khả thi.

Gọi ~cnt_x~ là số lần xuất hiện của ~x~ trong mảng. Với mỗi i, ~+1~ vào ~cnt_{a_i+b_i}~.

Tới đây có thể sử dụng nhiều ~CTDL~ như mảng, vector, unorderedmap,...

Chú ý: các phần tử có thể âm.

Độ phức tạp: ~O(m+n+q)~ hoặc ~O(m+nlogn+q)~.

Code tham khảo
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 1;

int n, m, q, a[N], b[N], cnt[3 * N], queries[N];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    memset(b, 0, sizeof b);
    memset(cnt, 0, sizeof cnt);

    cin >> n >> m >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i];

    while(m--) {
        int u, v, k;
        cin >> u >> v >> k;
        b[u] += k;
        b[v + 1] -= k;
    }

    int Amin = 1e9;
    for(int i = 1; i <= n; ++i)
        b[i] += b[i - 1],
        Amin = min(Amin, a[i] + b[i]);
    for(int i = 1; i <= q; ++i) cin >> queries[i], Amin = min(Amin, queries[i]);
    for(int i = 1; i <= n; ++i) ++cnt[a[i] + b[i] - Amin];

    for(int i = 1; i <= q; ++i) cout << cnt[queries[i] - Amin] << ' ';

    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.