# XÓA PHẦN TỬ

Trạng thái quy hoạch động sẽ là $f(i, j)$ nghĩa là xét đến vị trí thứ $i$, dãy đang có kết thúc là số $j$. Dễ thấy công thức của ta là:
- $f(i, j) = f(i - 1, j - 1) + f(i - 1, j)$ với $j = 1, 3$.
- $f(i, j) = f(i - 1, j - 1) + f(i - 1, j) * 2$ với $j = 2$ (số $2$ có thể xuất hiện kề nhau nhiều lần).

Kết quả bài toán là $f(n, 3)$

# CHIA KẸO - THT2024HN_CK_BC

## Hướng dẫn giải

### Subtask 1 (20%): $N, Q \le 10^3$

Với mỗi truy vấn, ta duyệt $i$ từ $l$ đến $r$ và thêm $x$ vào số kẹo của học sinh $i$ (gọi là $b[i]$) nếu $a[i]$ chia hết cho $x$.

Độ phức tạp: $O(N * Q)$

### Subtask 2 (20%): $x = 1$

Lúc này tất cả học sinh có số thứ tự từ $l$ đến $r$ đều nhận được kẹo, do đó ta sử dụng mảng hiệu và cập nhật `b[l] += v, b[r + 1] -= v` trong mỗi bước sau đó cộng dồn lại để được kết quả.

Độ phức tạp: $O(N + Q)$

### Subtask 3 (20%): $x \le 2$

Với $x = 1$, ta xử lý như Subtask 2

Với $x = 2$, ta lưu thêm một mảng $c$ là số kẹo của các học sinh có số thứ tự chẵn và cập nhật `c[l] += v, c[r + 1] -= v` tương tự như trên. Sau đó ta cộng dồn mảng $c$ và thêm $c[i]$ vào $b[i]$ nếu $i$ chẵn.

Độ phức tạp: $O(N + Q)$

### Subtask 4 (20%): $l = 1, r = N$

Vì $l = 1, r = N$ nên trong mỗi truy vấn, tất cả các học sinh có $a_i$ chia hết cho $x$ đều sẽ nhận được $v$ cái kẹo.

Gọi $f[i]$ là tổng số kẹo của các truy vấn có $x = i$, để tìm $f$ ta chỉ cần duyệt các truy vấn và cập nhật `f[x] += v`

Để tìm số kẹo của mỗi học sinh, với học sinh $i$ ta duyệt các ước $j$ của $a_i$ và thêm $f[j]$ vào kết quả. Nhưng cần chú ý $N \le 2 * 10^5, a_i \le 5 * 10^5$ nên nếu ta duyệt từ $1$ đến $\sqrt{a_i}$ thì sẽ không chạy kịp trong thời gian cho phép. Thay vào đó, ta xây dựng sẵn dãy ước của các số từ $1$ đến $5 * 10^5$ bằng các duyệt $i$ từ $1$ đến $5 * 10^5$ sau đó thêm $i$ vào dãy ước của các bội của $i$.

Độ phức tạp $O(N * max\{U(a_i)\} + Q)$

Code tham khảo:

#include<bits/stdc++.h>
#define el '\n'
using namespace std;

const int MN = 2e5 + 5;
const int N = 5e5 + 10;

int64_t ans[MN] , f[N];
int a[MN];
bool exist[N];
vector<int> divi[N];

int32_t main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n , q;
    cin >> n >> q;
    assert(n <= (int)2e5);
    for ( int i = 1 ; i <= n ; i++ ){
        cin >> a[i];
        exist[a[i]] = true;
    }
    int mx = *max_element(a + 1 , a + n + 1);
    for ( int64_t i = 1 ; i <= mx ; i++ ){
        for ( int64_t j = i ; j <= mx ; j += i ){
            if (exist[j]) divi[j].push_back(i);
        }
    }
    for ( int i = 1 ; i <= q ; i++ ){
        int l , r , x , y;
        cin >> l >> r >> x >> y;
        f[x] += y;
    }
    for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 0 ; j < divi[a[i]].size() ; j++ ){
            ans[i] += f[divi[a[i]][j]];
        }
    }
    for ( int i = 1 ; i <= n ; i++ ) cout << ans[i] << " ";
}

### Subtask 5 (20%): Không có ràng buộc gì thêm

Ta cải tiến từ Subtask 4 và sử dụng một kỹ thuật tương tự mảng hiệu

Vì lúc này không còn ràng buộc $l = 1, r = N$ nên mảng $f$ không còn giống nhau với tất cả học sinh, nhưng nếu ta tính mảng $f$ lần lươt cho các học sinh từ $1$ đến $N$ thì với mỗi truy vấn $l, r, x, v$, $f[x]$ được cộng thêm $v$ với tất cả học sinh từ $l$ đến $r$, nên ta chỉ cần cập nhật `f[x] += v` khi xử lý đến học sinh $l$ và cập nhật `f[x] -= v` khi xử lý đến học sinh $r + 1$.

Từ ý tưởng trên, đầu tiên với mỗi truy vấn $l, r, x, v$ ta chia thành hai truy vấn: `f[x] += v` được lưu vào danh sách các truy vấn tại $l$ và `f[x] -= v` được lưu vào danh sách các truy vấn tại $r + 1$. Sau đó, ta duyệt $i$ từ $1$ đến $N$ và lấy ra các truy vấn đã được lưu từ trước để cập nhật mảng $f$, sau đó duyệt các ước của học sinh $i$ để tìm số kẹo của học sinh $i$ tương tự như Subtask 4.

Độ phức tạp: $O(N * max\{U(a_i)\} + Q)$

## Code tham khảo

#include<bits/stdc++.h>
#define el '\n'
using namespace std;

const int MN = 2e5 + 5;
const int N = 5e5 + 10;

int64_t ans[MN] , f[N];
int a[MN];
bool exist[N];
vector<pair<int , int>> queries[MN];
vector<int> divi[N];

int32_t main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n , q;
    cin >> n >> q;
    assert(n <= (int)2e5);
    for ( int i = 1 ; i <= n ; i++ ){
        cin >> a[i];
        exist[a[i]] = true;
    }
    int mx = *max_element(a + 1 , a + n + 1);
    for ( int64_t i = 1 ; i <= mx ; i++ ){
        for ( int64_t j = i ; j <= mx ; j += i ){
            if (exist[j]) divi[j].push_back(i);
        }
    }
    for ( int i = 1 ; i <= q ; i++ ){
        int l , r , x , y;
        cin >> l >> r >> x >> y;
        queries[l].push_back(make_pair(x , y));
        queries[r + 1].push_back(make_pair(x , -y));
    }
    for ( int i = 1 ; i <= n ; i++ ){
        for ( int j = 0 ; j < queries[i].size() ; j++ ){
            f[queries[i][j].first] += queries[i][j].second;
        }
        for ( int j = 0 ; j < divi[a[i]].size() ; j++ ){
            ans[i] += f[divi[a[i]][j]];
        }
    }
    for ( int i = 1 ; i <= n ; i++ ) cout << ans[i] << " ";
}

# HÌNH CHỮ NHẬT - HNOI2021C2

## Hướng dẫn giải

### Subtask 1 (50%):

Ta duyệt các ô trái trên và ô phải dưới của hình chữ nhật con, sau đó duyệt qua hình chữ nhật con để tìm số lượng ký tự $'X'$ và cập nhật diện tích vào kết quả nếu hình chữ nhật con chỉ chứa một kỹ tự $'X'$

ĐPT: $O(N^3 * M^3)$

### Subtask 2 (30%):

Ta cải tiến việc tìm số lượng ký tự $'X'$ bằng mảng cộng dồn hai chiều

Ta duyệt hàng trên cùng và hàng dưới cùng của hình chữ nhật con, sau đó sử dụng hai con trỏ để tìm kết quả:

- Ta duyệt cột sát phải từ $1$ đến $M$, và duy trì một con trỏ lưu chỉ số cột sát trái nhỏ nhất mà hình chữ nhật con chỉ chứa một kỹ tự $'X'$
- Trong mỗi bước, ta tăng dần con trỏ đến khi hình chữ nhật con chỉ chứa một chữ $'X'$ thì dừng lại, và cập nhật diện tích vào kết quả

ĐPT: $O(N^2 * M)$

### Subtask 3 (20%):

Nhận xét: Các hình chữ nhật con tối ưu(không thể mở rộng về các phía) luôn bị chặn trên bởi một hàng chứa ký tự $'X'$ hoặc biên trên của hình chữ nhật lớn(hàng $'0'$) và bị chặn dưới bởi một hàng chứa ký tự $'X'$ hoặc biên dưới của hình chữ nhật lớn (hàng $N + 1$). Mà số ký tự $'X'$ $K \le 10^3$ nên chỉ có tối đa $10^3 + 2$ cận trên và dưới như vậy

Ta sẽ duyệt cận trên $i$ và cận dưới $j$ từ danh sách gồm các hàng chứa ký tự $'X'$, hàng $0$ và hàng $N + 1$ và tìm diện tích lớn nhất của các hình chữ nhật có hàng trên cùng là $i + 1$ và hàng dưới cùng là $j + 1$
- Ta tìm các cột chứa kí tự $'X'$ trong vùng giữa hàng $i$ và hàng $j$. Vì $K \le 10^3$ nên sẽ có tối đa $10^3$ cột này
- Với mỗi cột $y$ chứa ký tự $'X'$, ta tìm $pre[y]$ và $nxt[y]$ là hàng sát trái và sát phải nó chứa ký tự $'X'$. Khi đó kết quả là $ans = max\{(j - i - 1) * (nxt[y] - pre[y] - 1)\}$

Tuy nhiên, với thuật toán trên thì độ phức tạp vẫn là $O(K^3)$. Ta sẽ tìm cách cải tiến độ phức tạp xuống $O(K^2)$:
- Nếu ta duyệt từ $j$ tăng dần thì các khoảng $(pre[y], nxt[y])$ sẽ ngày càng hẹp lại (do số ký tự $'X,$ tăng lên) nhưng nếu duyệt $j$ giảm dần thì khoảng này sẽ ngày càng rộng ra. Do đó, ở mỗi bước ta có thể lưu lại $mx = max\{nxt[y] - pre[y] - 1\}$ và duyệt $j$ giảm dần sau đó sử dụng $mx$ của $j$ trước đó để cập nhật cho $j$ hiện tại
- Khi duyệt đến hàng $j'$ là hàng liền sau $j$ có chứa ký tự $'X'$, ta tính được kết quả cho vùng gồm các ký tự $'X'$ trên hàng $(i, j')$ hay $(i, j]$. Do đó, khi duyệt đến $j$ ta chỉ cần xóa các ký tự $'X'$ ở hàng $j$ là sẽ tính được kết quả cho vùng $(i, j)$. Ta sẽ lưu trữ một mảng $cnt[y]$ là số ký tự $X$ trên hàng $(i, j)$, cột $y$ và cập nhật $cnt$ để cập nhật $pre, nxt$ và $mx$. Ta duyệt các ký tự $X$ trên hàng $j$ và giảm dần $cnt[y]$ với $y$ là chỉ số cột của ký tự $'X'$
- Nếu $cnt[y] = 0$, ta xóa cột $y$ bằng cách cập nhật $pre[nxt[y]] = pre[y]$ và $nxt[pre[y]] = nxt[y]$ sau đó đưa $pre[y], nxt[y]$ vào một vector để cập nhật $mx$ (ta không thể cập nhật luôn vì sau đó $nxt[y]$ có thể bị xóa dẫn đến kết quả thay đổi)
- Nếu $cnt[y] = 1$, khi đó cột $y$ có thể dùng làm cột chứa ký tự $'X'$ trong hình chữ nhật con tối ưu, nên ta đưa cột $y$ vào vector trên
- Ta duyệt các cột $y$ trong vector và cập nhật $mx = max(mx, nxt[y] - pre[y] - 1)$ nếu $cnt[y] = 1$, sau đó cập nhật $ans = max\{(j - i - 1) * mx\}$

ĐPT: $O(K^2)$

## Code tham khảo

#include <bits/stdc++.h>
//#define int long long 
#define ld long double
#define pp pair<int, int> 
//#define endl "\n"

using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e4 + 7; 

int n, m, k;
vector<int> v[(int)(1e4 + 7)];
int cnt[maxn] = {0}, pre[maxn], nxt[maxn];
int ans = 0;
vector<int> rows, cols;

void program() {
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        int c, d;
        cin >> c >> d;
        v[c].emplace_back(d);
        rows.emplace_back(c);
        cols.emplace_back(d);
    }

    rows.emplace_back(0);
    rows.emplace_back(n + 1);
    sort(rows.begin(), rows.end());
    rows.erase(unique(rows.begin(), rows.end()), rows.end());
    sort(cols.begin(), cols.end());
    cols.erase(unique(cols.begin(), cols.end()), cols.end());

    for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end());

    for (int i_id = 0; i_id <= rows.size() - 2; i_id ++) {
        int i = rows[i_id];

        for (int y_id = 0; y_id <= cols.size() - 1; y_id++) {
            int y = cols[y_id];
            cnt[y] = 0;
            pre[y] = (y_id == 0) ? 0 : cols[y_id - 1];
            nxt[y] = (y_id == cols.size() - 1) ? m + 1 : cols[y_id + 1];
        }

        for (int x_id = i_id + 1; x_id <= rows.size() - 2; x_id ++) {
            int x = rows[x_id];
            for (auto y : v[x]) cnt[y] ++;
        }

        int mx = 0;

        for (auto y : cols) {
            if (cnt[y] == 0) {
                pre[nxt[y]] = pre[y];
                nxt[pre[y]] = nxt[y];
                if (cnt[pre[y]] == 1) mx = max(mx, nxt[y] - pre[pre[y]] - 1);
            }
            else if(cnt[y] == 1) mx = max(mx, nxt[y] - pre[y] - 1);
        }
        
        ans = max(ans, (n - i) * mx);

        for (int j_id = rows.size() - 2; j_id >= i_id + 2; j_id--) {
            int j = rows[j_id];

            vector<int> ud_cols;

            for (auto y : v[j]) {
                cnt[y] --;

                if (cnt[y] == 0) {
                    nxt[pre[y]] = nxt[y];
                    pre[nxt[y]] = pre[y];
                    ud_cols.emplace_back(pre[y]);
                    ud_cols.emplace_back(nxt[y]);
                }
                else if (cnt[y] == 1) ud_cols.emplace_back(y);
            }

            sort(ud_cols.begin(), ud_cols.end());
            ud_cols.erase(unique(ud_cols.begin(), ud_cols.end()), ud_cols.end());

            for (auto y : ud_cols) {
                if (cnt[y] == 1) mx = max(mx, nxt[y] - pre[y] - 1);
            }

            ans = max(ans, (j - i - 1) * mx);
        }
    }
    cout << ans;

}

signed main() {
    freopen("HCN.INP", "r", stdin);
    freopen("HCN.OUT", "w", stdout);

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    program();
}

# XÂY CẦU - bridges

## Khởi tạo
- Nếu nhà người $i$ và công ty của người $i$ cũng thuộc một vùng $(P[i] = Q[i])$ thì người này không cần qua cầu, tính khoảng cách của những người này.
$Res = Res + |P[i] - Q[i]|$, với $P[i] = Q[i]$
- Ta chỉ xét những người $i$ cần qua cầu $(P[i] ≠ Q[i])$, giả sử có $m$ người cần qua cầu, mất thêm $m$ đơn vị để $m$ người này qua cầu.
$Res = Res + m$

## Trường hợp ```K = 1```

### Subtask 1
- Giả sử có $m$ $(m ≤ n)$ người cần qua cầu, ta có thể có $2\times m$ vị trí xây cầu (có thể có những vị trí trùng nhau). Lần lượt thử $2\times m$ vị trí xây cầu, với mỗi vị trí ta tính khoảng cách của $n$ người đi qua cầu và so sánh với phương án tối ưu và được kết quả là $ans$.

- **Kết quả bài toán** $= Res + ans$.

**Độ phức tạp:** $O(n^2)$.

### Subtask 2
Vị trí đặt cầu tối ưu là trung vị của $2\times m$ vị trí có thể đặt cầu của $m$ người cần qua cầu. Sắp xếp $2\times m$ vị trí để tìm trung vị của nó.

**Độ phức tạp:** $O(n\log n)$.
<hr>

## Trường hợp ```K = 2```
- Gọi $a[i].x, a[i].y$ lần lượt $2$ vị trí đi, đến của người $i$ cần qua cầu. Giả sử có $m$ người cần qua cầu. Không mất tính tổng quát ta hoán đổi sao cho $a[i].x < a[i].y$.
- Sắp xếp dãy $a$ sao cho $a[i].x+a[i].y$ tăng dần.
- Khi đó sẽ tồn tại vị trí $i$ sao cho: Đặt cây cầu thứ nhất để từ người $1$ đến người $i$ sẽ đi qua cây cầu này, từ người thứ $i+1$ đến người thứ $n$ sẽ đi qua cây cầu thứ $2$ thì được khoảng cách bé nhất.
- Gọi $f[i] =$ khoảng cách nhỏ nhất để từ nhà $1$ đến nhà $i$ đi qua cây cầu thứ $1$.
- Gọi $h[i] =$ khoảng cách nhỏ nhất để từ nhà $i$ đến nhà $n$ đi qua cây cầu thứ $2$.
- **Kết quả bài toán** $= Res + min(f[i]+h[i+1])$, với $1 \le i \le n-1$.

### Subtask 3
Tính $f[i]$, $h[i]$ giống như trường hợp $K = 1$.

**Độ phức tạp:** $O(n^2\log n)$.

### Subtask 4
Cải tiến tính $f[i]$, $h[i]$ như sau:

Giả sử ta cần đặt $1$ cây cầu cho người thứ $1$ đến người thứ $i$ qua cầu $\Rightarrow$ ta cần tìm trung vị của $2\times i$ vị trí của $i$ người.

- Dùng $L$ : chứa $i$ vị trí nhỏ nhất trong $2\times i$ vị trí của $i$ người
- Dùng $R$: chứa $i$ vị trí lớn nhất trong $2\times i$ vị trí của $i$ người

$\Rightarrow$ Vị trí xây cầu sẽ ở vị trí lớn nhất trong $L$ hoặc vị trí nhỏ nhất trong $R$.

$\Rightarrow$ Khi đó tổng khoảng cách $=$ Tổng các số trong $R$ $–$ Tổng các số trong $L$.
Để tối ưu khi lấy phần tử nhỏ nhất trong $R$, lớn nhất trong $L$, Dùng Heapmin để lưu trữ $R$, và dùng Heapmax để lưu trữ $L$.

$\Rightarrow$ Khi xét đến người thứ $i$, ta cần cân bằng hai dãy này, nghĩa là phần tử lớn nhất trong $L$ nhỏ hơn hoặc bằng phần tử nhỏ nhất trong $R$.

**Độ phức tạp:** $O(n\log n)$.