# Bài 1. Tuyệt chiêu

## Tóm tắt đề bài

Cho dãy số nguyên dương $a_1,a_2,...,a_n$, và một số nguyên dương $k$. Khi đọc các số từ vị trí $1$ đến $n$, nếu tại vị trí $i$ đã xuất hiện số $a_i$, thì theo quy định, số $a_i$ chỉ có thể xuất hiện từ vị trí $i+k$ trở đi. Ngược lại, số đó được coi là đã **vi phạm** quy định.

Hãy cho biết số **nhỏ nhất** đã vi phạm quy định, hoặc cho biết rằng không có số nào vi phạm quy định (in ra $-1$).

Ví dụ, với $n=6$, $k=3$, và $a=[9,9,3,1,4,1]$, các số vi phạm quy định là $9$ (xuất hiện ở vị trí $1$, theo quy định chỉ xuất hiện từ vị trí $1+3=4$ trở đi, nhưng lại xuất hiện tiếp ở vị trí $2$) và $1$ (xuất hiện tại vị trí $4$ và $6$), trong đó số nhỏ nhất là $1$.

**Giới hạn:** $1\le n,a_i\le 10^6$; $1\le k\le 10^4$.

## Subtask 1: $n\le 10^3$

Với mỗi $i$, ta tìm vị trí $j<i$ gần nhất mà $a_j=a_i$. Nếu $i-j<k$ thì $a_i$ là một số vi phạm quy định, và ta chỉ cần cập nhật lấy min trong các số như vậy. Nếu duyệt $j$ đơn thuần (từ $i-1$ trở về) thì độ phức tạp tổng là $O(n^2)$.

## Subtask 2: $n\le 10^6$

Với mỗi số $x$, ta lưu lại $last[x]$ là vị trí xuất hiện gần nhất của nó trong mảng khi đi từ $1$ đến $n$. Ban đầu, ta khởi tạo $last[x]=0, \forall x=1..10^6$. Khi đó, vị trí $j$ cần tìm với mỗi $i$ là $last[a[i]]$ (nếu $last[a[i]]=0$ thì vị trí này không tồn tại). Sau khi kiểm tra và cập nhật đáp án xong, ta chỉ cần cập nhật lại: $last[a[i]]:=i$.

Khi này, mỗi lần duyệt $j$ như trên được thay thế bằng các thao tác có độ phức tạp $O(1)$, nên tổng độ phức tạp thời gian là $O(n)$.

:::spoiler **Code mẫu**

#include <bits/stdc++.h>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mxn = 1e6 + 3;
const int inf32 = 2e9;
int n, k, a[mxn], last[mxn];
void solve(){
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int res = inf32;
    for (int i = 1; i <= n; ++i){
        if (last[a[i]] != 0 && i - last[a[i]] < k){
            res = min(res, a[i]);
        }
        last[a[i]] = i;
    }
    if (res == inf32) cout << -1;
    else cout << res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("tuyetchieu.inp", "r", stdin);
    freopen("tuyetchieu.out", "w", stdout);
    solve();
    return 0;
}

:::

# Bài 2. Đắp núi

## Tóm tắt đề bài

Cho dãy số nguyên không âm $A_1,A_2,...,A_n$. Trong một thao tác, có thể chọn một chỉ số $i$ và tăng $A_i$ lên $1$. Hãy tìm số thao tác nhỏ nhất cần thực hiện sao cho: tồn tại chỉ số $x$ ($1<x<n$) để $A_1<A_2<...<A_x>A_{x+1}>...>A_n$ (khi này, dãy $A$ được gọi là một ngọn núi, với vị trí $x$ là đỉnh núi).

Ví dụ, với $n=5$ và $a=[1,1,1,1,1]$, có thể biến đổi dãy thành $[1,2,3,2,1]$ trong $4$ thao tác:
+ chọn $i=2$ một lần, dãy trở thành $[1,2,1,1,1]$;
+ chọn $i=3$ hai lần, dãy trở thành $[1,2,3,1,1]$;
+ chọn $i=4$ một lần, dãy trở thành $[1,2,3,2,1]$.

**Giới hạn:** $3\le n\le 10^5$; $0\le A_i\le 10^9$.

## Subtask 1: $n\le 10^3$

Với mỗi $x=2,...,n-1$, ta sẽ thử biến đổi dãy sao cho vị trí $i$ là đỉnh núi của dãy. Có nghĩa là, ta cần phải làm sao cho hai dãy $A_1,A_2,...,A_x$ và $A_n,A_{n-1},...,A_x$ là tăng đơn điệu.

Hai bài toán con này là giống nhau, nên ta chỉ nói về bài toán con thứ nhất. Để làm cho dãy $A_1,A_2,...,A_x$ tăng đơn điệu trong số thao tác tối thiểu, ta có thể sử dụng thuật toán tham lam. Ta sẽ duyệt $i$ từ $1$ đến $x$, và xét trường hợp như sau:
+ nếu $A_i\le A_{i-1}$: ta tối thiểu số thao tác bằng cách chỉ tăng $A_i$ lên bằng $A_{i-1}+1$ (để thỏa điều kiện tăng), nên ta sử dụng $A_{i-1}+1-A_i$ thao tác cho $A_i$.
+ nếu $A_i>A_{i-1}$: ta không cần thực hiện thao tác nào cả.

Vậy, ta cần duyệt qua cả mảng để tính đáp án cho việc chọn $x$ làm đỉnh núi, và ta sẽ chọn đáp án nhỏ nhất. Độ phức tạp thời gian của thuật toán này là $O(n^2)$.

:::spoiler **Cài đặt Subtask 1**

ll res = inf64;
for (int x = 2; x <= n - 1; ++x){
    ll cur = 0;
    for (int i = 2; i <= x; ++i){
        if (a[i] <= a[i - 1]){
            cur += (a[i - 1] + 1 - a[i]);
            a[i] = a[i - 1] + 1;
        }
    }
    for (int i = n - 1; i >= x; --i){
        if (a[i] <= a[i + 1]){
            cur += (a[i + 1] + 1 - a[i]);
            a[i] = a[i + 1] + 1;
        }
    }
    
    res = min(res, cur);
    // khôi phục dãy a ban đầu
}
cout << res << '\n';

:::

## Subtask 2: $n\le 10^5$

Từ thuật toán của Subtask 1, ta thấy rằng với mỗi $x$, ta tìm số thao tác tối thiếu để làm cho tiền tố $[1..x]$ tăng dần và hậu tố $[x..n]$ giảm dần. Tuy nhiên, mỗi khi $x$ thay đổi thì ta lại tính lại hoàn toàn số thao tác. Vậy nên, nếu ta có thể cố gắng lưu lại thông tin đã tính được từ $x$ trước đó, hoặc tiền xử lý thông tin gì đó, thì ta có thể tối ưu độ phức tạp.

Gọi $dp(i,0)$ là số thao tác tối thiểu để làm cho tiền tố $[1..i]$ của dãy tăng dần, và gọi $h(i,0)$ là giá trị nhỏ nhất của $A_i$ trong cách làm cho tiền tố $[1..i]$ tăng dần với số thao tác tối thiểu đó. Định nghĩa $dp(i,1)$ và $h(i,1)$ tương tự, nhưng là với hậu tố $[i..n]$ của dãy giảm dần.

Không khó thấy rằng việc tính các mảng này rất giống với việc tính số thao tác như trong Subtask 1. Cụ thể, xét trên tiền tố $[1..i]$, ta có công thức như sau:
+ nếu $A_i\le h(i-1,0)$, thì ta cần làm cho $A_i$ ít nhất bằng $h(i-1,0)+1$, vậy $h(i,0)=h(i-1,0)+1$ và $dp(i,0)=dp(i-1,0)+h(i-1,0)+1-A_i$.
+ ngược lại, $A_i>h(i-1,0)$, thì dễ thấy $h(i,0)=A_i$ và $dp(i,0)=dp(i-1,0)$.

Đương nhiên, cách tính $dp(i,1)$ và $h(i,1)$ cũng rất giống như trên nên ta sẽ bỏ qua công thức chính xác khi này.

Khi chọn vị trí $x$ làm đỉnh núi, ta biết rằng ta đã sử dụng $dp(x-1,0)$ thao tác để làm cho $[1..x-1]$ tăng dần, và $dp(x+1,1)$ thao tác để làm cho $[x+1..n]$ giảm dần. Thế, để đảm bảo cả dãy là ngọn núi, ta cần $A_i>h(x-1,0)$ và $A_i>h(x+1,1)$, nên nếu $A_i>\max(h(x-1,0),h(x+1,1))$ thì ta không cần thay đổi $A_i$, ngược lại giá trị nhỏ nhất cho $A_i$ là $\max(h(x-1,0),h(x+1,1))+1$.

Độ phức tạp thời gian của thuật toán là $O(n)$.

:::spoiler **Code mẫu**

#include <bits/stdc++.h>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mxn = 1e5 + 3;
const ll  inf64 = 7e18;
int n;
ll a[mxn], dp[2][mxn], h[2][mxn];
void solve(){
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    dp[0][1] = 0, h[0][1] = a[1];
    for (int i = 2; i <= n; ++i){
        if (a[i] <= h[0][i - 1]){
            dp[0][i] = dp[0][i - 1] + (h[0][i - 1] - a[i] + 1);
            h[0][i] = h[0][i - 1] + 1;
        } else {
            dp[0][i] = dp[0][i - 1];
            h[0][i] = a[i];
        }
    }
    dp[1][n] = 0, h[1][n] = a[n];
    for (int i = n - 1; i >= 1; --i){
        if (a[i] <= h[1][i + 1]){
            dp[1][i] = dp[1][i + 1] + (h[1][i + 1] - a[i] + 1);
            h[1][i] = h[1][i + 1] + 1;
        } else {
            dp[1][i] = dp[1][i + 1];
            h[1][i] = a[i];
        }
    }
    ll res = inf64;
    for (int i = 2; i <= n - 1; ++i){
        ll f;
        if (max(h[0][i - 1], h[1][i + 1]) < a[i]) f = 0;
        else f = max(h[0][i - 1], h[1][i + 1]) + 1 - a[i];
        res = min(res, dp[0][i - 1] + dp[1][i + 1] + f);
    }
    cout << res << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("dapnui.inp", "r", stdin);
    freopen("dapnui.out", "w", stdout);
    solve();
    return 0;
}

:::

# Bài 3. Lọc nước

## Tóm tắt đề bài

Có $n$ hệ thống lưu giữ nước, hệ thống thứ $i$ ($1\le i\le n$) ban đầu có $a_i$ lít nước.

Mỗi hệ thống có cấu tạo giống nhau. Mỗi hệ thống đều có $m$ bồn chứa nước, bồn thứ $i$ có dung tích là $r_i$ lít. Nước từ các hệ thống được truyền lần lượt qua các bồn theo thứ tự từ bồn $1$ đến $m$.

Với nước từ mỗi hệ thống, nước sẽ chảy vào bồn $1$ trước, và chừng nào bồn $1$ đã đầy thì mới chảy tiếp vào bồn $2$, và cứ như vậy đến bồn thứ $m$. Cũng có thể còn nước dư, nhưng không còn lại bồn nào sẽ chứa lượng nước đó.

Có $m$ máy xử lý nước, máy thứ $i$ thu nhận và xử lý nước của các bồn được đánh số $i$ trong các hệ thống. Hỏi, mỗi máy xử lý nước đã thu nhận bao nhiêu lít nước?

Cụ thể, ta cần cho biết lần lượt máy thứ $1$, máy thứ $2$,... đã thu nhận bao nhiêu nước, nhưng tới máy nào mà không thu nhận được nước thì ta không cần cho biết lượng nước các máy tiếp theo thu nhận được (vì ta biết ngay nó là $0$ lít).

Ví dụ, với $n=4$, $m=5$, $a=[6,8,2,5]$, và $r=[4,3,2,7,6]$, quá trình diễn ra như sau:
+ Các bồn nước số $1$: với dung tích là $4$ lít, các hệ thống đưa vào các bồn số $1$ tương ứng lần lượt là $4,4,2,4$ lít nước, vậy máy xử lý $1$ thu nhận $4+4+2+4=14$ lít nước. Các hệ thống còn lại $[2,4,0,1]$ lít nước.
+ Các bồn nước số $2$: với dung tích là $3$ lít, các hệ thống đưa vào các bồn số $2$ tương ứng lần lượt là $2,3,0,1$ lít nước, vậy máy xử lý $2$ thu nhận $2+3+0+1=6$ lít nước. Các hệ thống còn lại $[0,1,0,0]$ lít nước.
+ Các bồn nước số $3$: với dung tích là $2$ lít, các hệ thống đưa vào các bồn số $3$ tương ứng lần lượt là $0,1,0,0$ lít nước, vậy máy xử lý $3$ thu nhận $0+1+0+0=1$ lít nước. Các hệ thống còn lại $[0,0,0,0]$ lít nước.

Khi này, các hệ thống đều không còn nước, nên ta không cần quan tâm tới máy xử lý $4$ và $5$, mà ta chỉ cần cho biết lần lượt: $14,6,1$.

**Giới hạn:** $1\le n \le2\times10^5$; $1\le m\le 10^9$; $a_i,r_i\le 10^5$ **(chú ý giới hạn $m$)**.

## Subtask 1: $n\le 10^3,m\le10^2$

Với subtask này, "đề kêu gì thì ta làm nấy". Ta chỉ cần tính lần lượt đáp án cho các máy xử lý nước, với độ phức tạp là $O(n\times m)$.

:::spoiler **Cài đặt Subtask 1**

for (int i = 1; i <= m; ++i){
    ll cur = 0;
    for (int j = 1; j <= n; ++j){
        if (a[j] <= r[i]) cur += a[j], a[j] = 0;
        else cur += r[i], a[j] -= r[i];
    }
    if (cur == 0) break;
    cout << cur << ' ';
}

:::

## Subtask 2: $n\le 10^3, m\le10^9$

Với subtask này, ta không tài nào có thể lưu được cả mảng $r$. Tuy nhiên, để ý rằng trong Subtask 1, ta cũng có thể xử lý một cách **online**: ta nhập $r_i$ đến đâu, ta tính luôn đáp án với máy xử lý $i$ (nói cách khác, ta không hề cần lưu lại mảng $r$).

Trong trường hợp tệ nhất, $a=[10^5,10^5,...,10^5]$ và $r=[1, 1,...,1]$, thì ta cần đến máy xử lý $10^5$ để tất cả hệ thống không còn nước, vậy độ phức tạp xấu nhất là $O(n\times 10^5)$.

## Subtask 3: $n\le 2\times10^5,m\le10^9$

Nhận thấy rằng, hệ thống có càng nhiều nước lúc ban đầu thì sẽ qua nhiều máy xử lý hơn tới khi nó hết nước. Vì thế, trước tiên, ta sẽ sắp xếp lại mảng $a$ tăng dần.

Xét dãy $[a_1,a_2,...,a_n]$ trước khi đưa qua máy xử lý dung tích $r$. Ta có thể chia dãy $a$ làm ba phần riêng biệt:
1. một tiền tố của $a$ mà toàn $0$;
2. một đoạn ở giữa của $a$, trong đó $0< a_i\le r$;
3. một hậu tố của $a$, trong đó $a_i>r$.

Hơn nữa, dễ thấy rằng sau mỗi lần đưa qua một máy xử lý nước thì dãy $a$ vẫn là dãy không giảm. Vì thế, ta có thể xác định ba đoạn này sử dụng thuật toán **tìm kiếm nhị phân**. Cụ thể, ta cần tìm chỉ số $L$ nhỏ nhất thỏa $a_L>0$, và chỉ số $H$ nhỏ nhất thỏa $a_H>r$. Khi đó, các đoạn lần lượt là $[1,L-1],[L,H-1],[H,n]$. Không khó thấy, lượng nước máy xử lý này thu nhận bằng $(a_L+a_{L+1} + … + a_{H-1}) + r\times(n-H+1)$.

Với ý tưởng này thì ta vẫn cần phải trực tiếp trừ các $a_i$ đi $r$ ($H\le i\le n$) nên độ phức tạp vẫn chưa tối ưu. Để ý rằng ta áp dụng việc trừ $r$ lên cả mảng, nên ta có thể làm như sau.

Giả sử sau mỗi máy xử lý nước dung tích $r$, ta thực hiện: $a_i:=a_i-r$, với mọi $i=1,2,…,n$. Khi đó, đoạn duy nhất của $a$ thay đổi là tiền tố, trong đó $a_i<0$. Vậy, ta sẽ lưu lại biến $sumR$ là tổng dung tích tất cả các bồn trước bồn đang xét. Khi đó, không thay đổi mảng $a$, các phần được nhắc đến ở trên thay đổi thành:
1. một tiền tố của $a$, trong đó $a_i<sumR$;
2. một đoạn ở giữa của $a$, trong đó $sumR\le a_i\le sumR+r$;
3. một hậu tố của $a$, trong đó $a_i>sumR+r$.

Vai trò của các đoạn hoàn toàn giống như trên, chỉ khác là ở đây, ta không thay đổi dãy $a$, mà lưu sự thay đổi đó vào biến $sumR$. Và bây giờ, $L$ là chỉ số nhỏ nhất thỏa $a_L\ge sumR$, và $H$ là chỉ số nhỏ nhất thỏa $a_H>sumR+r$. Lượng nước máy thu nhận được giống như trên, nhưng ta phải trừ đi $sumR\times(H-L)$ trong đoạn thứ hai; hơn nữa, ta có thể sử dụng tổng tiền tố để tính tổng các $a_i$ liên tiếp nhanh chóng.

Độ phức tạp thời gian của thuật toán tối ưu là $O(n+10^5\times\log n)$.

:::spoiler **Code mẫu**

#include <bits/stdc++.h>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mxn = 2e5 + 3;
int n, m;
ll a[mxn], pref[mxn];
void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
        pref[i] = pref[i - 1] + a[i];
    ll sumR = 0, r;
    for (int _ = 1; _ <= m; ++_){
        cin >> r;
        int L = lower_bound(a + 1, a + n + 1, sumR) - a;
        int H = upper_bound(a + 1, a + n + 1, sumR + r) - a;
        ll cur = (pref[H - 1] - pref[L - 1]) + r * (n - H + 1) - sumR * (H - L);
        if (cur == 0) break;
        cout << cur << ' ';
        sumR += r;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("locnuoc.inp", "r", stdin);
    freopen("locnuoc.out", "w", stdout);
    solve();
    return 0;
}

:::