---
title
Mảng cộng dồn và mảng hiệu - Lời giải
---

Mảng cộng dồn và mảng hiệu - Lời giải
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Bài 1: [VNOJ - GIRLS](https://oj.vnoi.info/problem/bedao_m06_girls)
#### **Tóm tắt đề:**
Cho mảng 1 chiều $A$ kích thước $M$, số nguyên dương $N$ và số nguyên không âm $K$. Chọn ra $N$ phần tử sao cho hiệu giữa phần tử lớn nhất và nhỏ nhất (trong số các phần tử được chọn) không vượt quá $K$ và tổng của $N$ phần tử được chọn phải lớn nhất. Nếu không tồn tại cách chọn thì in ra $-2$.
#### **Input**
- Dòng đầu gồm 3 số nguyên $N, M, K$ $(1 \le N \le M \le 10^6, 0 \le K \le 10^8)$.
- Dòng thứ 2 gồm $M$ phần tử $A_i$ $(0 \le A_i \le 10^8)$.
#### **Output**
- Dòng duy nhất chứa số nguyên là đáp án, nếu không tồn tại đáp án in ra $-2$.
#### **Sample testcase**
- Input:

3 2 1
1 2 3

- Output:

5

:::spoiler **Hướng dẫn giải**
- Đầu tiên, ta sắp xếp lại mảng $A$ theo thứ tự tăng dần rồi xây dựng mảng cộng dồn 1 chiều $pref$ theo mảng $A$ đã được sắp xếp.
- Sau đó, ta duyệt qua mỗi $N$ phần tử liên tiếp trong mảng $A$ - một **cửa sổ trượt** (sliding window) có độ dài $N$ - rồi kiểm tra xem hiệu giữa hai phần tử đầu và cuối (tức phần tử lớn nhất và nhỏ nhất trong $N$ phần tử đang xét do ta đã sắp xếp lại toàn bộ mảng) có thỏa mãn điều kiện $\le K$ hay không, nếu thỏa ta sẽ cập nhật lại đáp án bằng cách tính tổng của dãy con được chọn (sử dụng mảng cộng dồn $pref$ đã xây dựng).
:::
:::spoiler **Code mẫu**

#include <bits/stdc++.h>

using namespace std;

const int MaxM = 1e6 + 1;

int M, N, K, A[MaxM];
long long pref[MaxM];

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

  cin >> M >> N >> K;
  for(int i = 1; i <= M; ++i) cin >> A[i];

  sort(A + 1, A + 1 + M);

  for(int i = 1; i <= M; ++i)
    pref[i] = pref[i - 1] + A[i];

  long long ans = -2;
  for(int i = N; i <= M; ++i)
  {
    if(A[i] - A[i - N + 1] <= K)
        ans = max(ans, pref[i] - pref[i - N]);
  }
  cout << ans;

  return 0;
}

:::

# Bài 2: [Codeforces - Greg and Array](https://codeforces.com/contest/296/problem/C)
#### **Tóm tắt đề:**
Cho 1 mảng 1 chiều $a$ gồm $n$ phần tử, $m$ thao tác với mỗi thao tác gồm 3 giá trị $l_i, r_i, d_i (1 \le l_i \le r_i \le n)$ biểu diễn cho việc tăng 1 giá trị $d_i$ với cho mỗi phần tử trong mảng $a$ từ trong đoạn $[l_i, r_i]$. Sau đó gồm $k$ truy vấn, với mỗi truy vấn cho 2 số $x_i, y_i$. Nghĩa là mỗi truy vấn sẽ thực hiện các thao tác $x_i, x_{i+1}, x_{i+2},...,y_i$ lên mảng $a$
#### **Input**
- Dòng đầu gồm 3 số nguyên $n, m, k$ $(1 \le n, m, k \le 10^5)$. Dòng thứ 2 gồm $n$ phần tử $a_i$ $(0 \le a_i \le 10^5)$
- $m$ dòng tiếp theo chứa các thao tác, thao tác thứ $i$ chứa 3 số nguyên $l_i, r_i, d_i$ $(1 \le l_i,r_i \le n)$, $(0 \le d_i \le 10^5)$
- $k$ dòng tiếp theo chứa các truy vấn, truy vấn thứ $i$ gồm 2 số $x_i, y_i$ $(1 \le x_i, y_i \le m)$
#### **Output**
- Dòng duy nhất gồm $n$ số nguyên $a_1, a_2,...,a_n$: mảng $a$ sau khi thực hiện tất cả các truy vấn. Các số được in cách nhau 1 dấu cách.
#### **Sample testcase**
- Input:

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3

- Output:

9 18 17

:::spoiler **Hướng dẫn giải**
Dùng 2 mảng hiệu `operations_count` và `dif` để lưu trữ. Mảng `operations_count` để lưu số lần thực hiện thao tác, mảng `dif` để lưu các giá trị được thay đổi trên đoạn $[1, n]$. Sau đó thực hiện cộng dồn mảng `dif` và với mỗi phần tử $i$ của mảng $a$, cộng với $dif_i$ và xuất ra kết quả.
:::
:::spoiler **Cài đặt**

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

#define ll long long

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    ll n, m, k; cin >> n >> m >> k;

    vector <pair<ll, ll>> operations(m+1);
    vector <ll> val(m+1), operations_count(m+3), a(n+1); // mảng operations_count phải có ít nhất m+1 phần tử do y <= m ===> y+1 <= m+1

    for (ll i = 1; i <= n; ++i) cin >> a[i];
    for (ll i = 1; i <= m; ++i) cin >> operations[i].first >> operations[i].second >> val[i];

    for (ll i = 1; i <= k; ++i)
    {
        ll x, y; cin >> x >> y;
        operations_count[x]++;
        operations_count[y + 1]--;
    }

    vector <ll> dif(n+3); // mảng dif phải có ít nhất n+1 phần tử với lí do tương tự như mảng operations_count
    for (ll i = 1; i <= m; ++i)
    {
        operations_count[i] += operations_count[i-1];
        if (operations_count[i] > 0)
        {
            ll l = operations[i].first, r = operations[i].second + 1;
            dif[l] += val[i] * operations_count[i];
            dif[r] -= val[i] * operations_count[i];
        }
    }
    for (ll i = 1; i <= n; ++i)
    {
        dif[i] += dif[i-1];
        a[i] += dif[i];
        cout << a[i] << ' ';
    }
    return 0;
}

:::

# Bài 3: [VNOJ - CHIADAT](https://oj.vnoi.info/problem/olp304_18_chiadat//)
#### **Tóm tắt đề:**
Cho một mảng 2 chiều $A$ kích thước $N * N$ chỉ chứa các giá trị $0$ và $1$. Tìm cách chia mảng $A$ thành 4 phần sao cho chênh lệch giữa phần có tổng giá trị (tổng giá trị các phần tử nằm trong phần đó) lớn nhất nhất và phần có tổng giá trị nhỏ nhất là nhỏ nhất.
#### **Input**
- Dòng đầu gồm 1 số nguyên $N$ $(N \le 500)$.
- $N$ dòng tiếp theo, mỗi dòng chứa $N$ phần tử $A_{ij}$ $(A_{ij} \in$ {$0, 1$}$)$.
#### **Output**
- Dòng duy nhất chứa số nguyên là đáp án.
#### **Sample testcase**
- Input:

6
1 0 1 0 0 1
0 1 0 0 0 1
1 0 0 0 0 0
0 1 1 0 0 1
0 1 0 0 1 0
1 0 1 0 0 0

- Output:

1

:::spoiler **Hướng dẫn giải**
- Đầu tiên, ta xây dựng mảng cộng dồn 2 chiều $pref$ của mảng $A$.
- Sau đó, duyệt qua mọi phần tử của mảng $A$ và lấy vị trí ${x, y}$ của phần thử đó làm tâm của 2 đường cắt chia mảng $A$ thành 4 phần. Gọi tổng của các phần tử nằm trong các phần đó lần lượt là $S_1, S_2, S_3, S_4$, ta có $S_1 = \sum_{i = 1}^{x} \sum_{j = 1}^{y} A_{ij}, S_2 = \sum_{i = 1}^{x} \sum_{j = y + 1}^{N} A_{ij}, S_3 = \sum_{i = x + 1}^{N} \sum_{j = 1}^{y} A_{ij}, S_4 = \sum_{i = x + 1}^{N} \sum_{j = y + 1}^{N} A_{ij}$
- Ta tính $S_1, S_2, S_3, S_4$ (sử dụng mảng cộng dồn $pref$ đã xây dựng) rồi so sánh **chênh lệch** giữa phần có giá trị lớn nhất ($max(S_1, S_2, S_3, S_4)$) và phần có giá trị nhỏ nhất ($min(S_1, S_2, S_3, S_4)$) với đáp án hiện tại đang có, nếu chênh lệch đó nhỏ hơn đáp án thì ta cập nhật đáp án.
:::
:::spoiler **Code mẫu**
*(Lưu ý: bài này nhập xuất dữ liệu bằng file)*

#include <bits/stdc++.h>

using namespace std;

const int MaxN = 5e2 + 5;
int N;
long long A[MaxN][MaxN], pref[MaxN][MaxN], S[5], maxS, minS, ans;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    freopen("CHIADAT.INP", "r", stdin); //nhap du lieu bang file
    freopen("CHIADAT.OUT", "w", stdout); //xuat du lieu bang file
    
    cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            cin >> A[i][j];
            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + A[i][j];
        }
    }
    ans = 1e18;
    for (int i = 1; i <= N - 1; i++)
    {
        for (int j = 1; j <= N - 1; j++)
        {
            S[1] = pref[i][j];
            S[2] = pref[i][N] - pref[i][j];
            S[3] = pref[N][j] - pref[i][j];
            S[4] = pref[N][N] - pref[i][N] - pref[N][j] + pref[i][j];
            maxS = max({S[1], S[2], S[3], S[4]});
            minS = min({S[1], S[2], S[3], S[4]});
            ans = min(ans, maxS - minS);
        }
    }
    cout << ans;

    return 0;
}

:::