# **Editorial for 2024 TS10_Ju Problemset #3(Pre Tuyển Sinh 6)**

**[F1 - Khách sạn của Steph](https://codeforces.com/gym/527354/problem/F1)**

++Đề bài++:

Trong 1 ngày bạn chỉ cần quản lý khoảng thời gian từ 1 đến n. Trong khoảng thời gian đó sẽ có $m$ khách hàng check-in $l_i$ và check-out $r_i$ $(l_i \le r_i)$. Giả sử rằng khách sạn có vô hạn phòng trống để khách hàng luôn có phòng trống để nghỉ ngơi. Mỗi ngày sẽ có 1 đoàn thanh tra đến kiểm tra chất lượng của khách sạn bằng cách đưa ra $q$ câu hỏi để bạn phải trả lời. Với mỗi truy vấn, đoàn sẽ hỏi một số $x$ với ý nghĩa có bao nhiêu khách hiện tại đang ở trong khách sạn tại thời điểm $x$.

- Với subtask 1 ta có thể vét với độ phức tạp $O(n * q)$.
- Với subtask 2 ta dùng tư tưởng prefix sum với độ phức tạp $O(n + q)$.
- Với subtask 3:

++Ý tưởng++: Ta lật ngược bài toán lại, với mỗi xem có bao nhiêu khách hàng không có mặt tại thời điểm $x$, nói cách khác: đếm những trường hợp thỏa mãn $l_i > q_i$ hoặc $r_i < q_i$. Bài toán này đã trở thành một bài toán đơn giản hơn rất nhiều. Ta có thể sắp xếp mảng $l, r$ độc lập nhau và dùng tìm kiếm nhị phân để cho ra $ans$. Vậy đáp án của bài toán gốc là $n - ans$. Vì sao lại có thể sắp xếp mảng $l,r$ độc lập nhau? Vì ta luôn có $(l_i \le r_i)$ nên khi tìm kiếm nhị phân nên không có trường hợp nào trùng nhau. Độ phức tạp của thuật toán này là $O(q.logn)$.

#include <bits/stdc++.h>

using namespace std;

const int maxN = 2 * 1e5 + 17;

int n,m,q;
int l[maxN], r[maxN];
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("HOTEL.inp","r",stdin);
    freopen("HOTEL.out","w",stdout);
    
 
    cin >> n >> m >> q;
    for (int i = 1; i <= m; ++i) cin >> l[i] >> r[i];
 
    sort(l + 1, l + 1 + m);
    sort(r + 1, r + 1 + m);
 
    while (q--)
    {
        ll k;
        cin >> k;
        int ans1 = m - (upper_bound(l + 1, l + 1 + m, k) - l) + 1; //Tìm những trường hợp li > qi
        int ans2 = (lower_bound(r + 1, r + 1 + m, k) - r) - 1; //Tìm những trường hợp ri < qi
        cout << m - ans1 - ans2 << endl;
    }
 
    return 0;
}

**[F2 - Nhiệm vụ kì lạ từ Steph](https://codeforces.com/gym/527354/problem/F2)**

++Đề bài++:

Ta định nghĩa $f(l,r) = max(a_l, a_{l + 1}, ..., a_{r - 1}, a_r) - min(a_l, a_{l + 1}, ..., a_{r - 1}, a_r)$

Tính $\sum\limits_{l = 1}^{n} \sum\limits_{r = l + 1}^{n} f(l,r)$.

- Với subtask 1 ta có thể vét với độ phức tạp $O(n^3)$.
- Với subtask 2 ta vét khôn khéo hơn một chút cho ra thuật với độ phức tạp $O(n^2)$.
- Với subtask 3:

++Ý tưởng++: Ta chia thành 2 bài toán nhỏ hơn đó là tính tổng max và tính tổng min. Ta lấy ví dụ $A = \{3, 1, 9, 6, 5, 8, 2\}$ và lấy vị trí $i = 4$ có $a_4 = 6$. Vậy khi nào nó là max của một đoạn con liên tiếp? Khi đoạn con đó nằm trong đoạn $[4,5]$. Vì sao thế? Gọi $l_{first}$ là vị trí đầu tiên bên trái mà lớn hơn $a_4$; $r_{first}$ là vị trí đầu tiên bên phải mà lớn hơn $a_4$. Vậy $l_{first} = 3, r_{first} = 6$. Vì khi đoạn con có chứa vị trí $l_{first} = 3$ hoặc $r_{first} = 6$ thì $a_4$ không còn là max của đoạn con đó nữa. Cho dù giảm $l_{first}$ hay tăng $r_{first}$ thì $a_4$ vẫn sẽ luôn luôn không phải max của đoạn con đó. Và điều cuối cùng là tính xem có bao nhiêu đoạn con trong đoạn $[4,5]$ có chứa vị tri $i = 4$. Ta dùng tổ hợp đó là $(4 - 4 + 1) * (5 - 4 + 1) = [4 - (4 - 1)] * [(5 + 1) - 4] = (4 - 3) * (6 - 4) = 2$. Ta rút ra được công thức tính số đoạn con chứa $i = 4$ mà nằm trong $[l_{first} - 1, r_{first} + 1]$ là $(i - l_{first}) * (r_{first} - i)$. Tương tự như vậy với cách tìm tổng min/max cho từng $i$. Ta nên xét $i$ theo $a_i$ từ max -> min và từ min -> max để tiện cập nhật.

Ta có thể làm điều này thông qua dùng stack, set, implementation,... Độ phức tạp khi dùng ý tưởng này và set theo code dưới đây là $O(n.logn)$.

#include <bits/stdc++.h>

using namespace std;

const int maxN = 2 * 1e5 + 17;
const long long MOD = 1e9 + 7;

int n;
long long a[maxN];
set<long long> id;
vector<pair<long long, long long>> m;
long long ans_mi = 0, ans_ma = 0;
 
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        m.push_back({a[i],i});
    }
    sort(m.begin(), m.end());
 
    //Min
    id.insert(0), id.insert(n + 1);
    for (auto [v,i] : m)
    {
        auto it = id.upper_bound(i);
        ans_mi += (( ( ((*it) - i) * (i - (*(--it))) )% MOD) * v) % MOD;
        ans_mi %= MOD;
        id.insert(i);
    }
 
    //Max
    id.clear(), reverse(m.begin(), m.end());
    id.insert(0), id.insert(n + 1);
    for (auto [v,i] : m)
    {
        auto it = id.upper_bound(i);
        ans_ma += (( ( ((*it) - i) * (i - (*(--it))) )% MOD) * v) % MOD;
        ans_ma %= MOD;
        id.insert(i);
    }
 
    cout << (ans_ma - ans_mi + MOD) % MOD;
    return;
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("PROFIT.inp","r",stdin);
    freopen("PROFIT.out","w",stdout);
    
    solve();
 
    return 0;
}

**[F3 - Thiết kế độc đáo cho Steph](https://codeforces.com/gym/527354/problem/F3)**

++Đề bài++:

Gần đây ông Steph đang có kế hoạch thiết kế lại mọi thứ trong khách sạn. Thứ mà ông hay chú ý nhất đó là lối đi vào khách sạn. Với một lát gạch có kích thước 1 * 1 thì ông muốn lát n gạch trên cùng 1 hàng song song vối lối đi. Ban đầu lát gạch chưa có màu gì. Lát gạch sẽ có 2 màu, đó là trắng và đen. Ông Steph là một người khá mê tín nên ông muốn lát gạch mà đảm bảo 2 tiêu chí sau:

* Nếu xét x lát gạch liên tiếp cùng màu bất kì, điều kiện (k ≥ x) luôn thỏa.
* Sẽ có m lát gạch bắt buộc phải là màu đen, đó có thể là những lát gạch bất kì đánh số từ 1 đến n.

Hãy giúp ông Steph có bao nhiêu cách lát gạch khác nhau thỏa mãn 2 tiêu chí trên.

- Với subtask 1: Ta có thể vét mọi trường hợp và kiểm tra 2 tiêu chí trên với độ phức tạp $O(2^n.n)$
- Với subtask 2,3,4,5:

++Ý tưởng++:

Gọi $dp_0(i)$ là số cấu hình lát gạch đến ô thứ $i$ và ô thứ $i$ màu trắng thỏa yêu cầu bài toán. Tương tự, ta có định nghĩa $dp_1(i)$ tương ứng với ô thứ $i$ màu đen.
Ở ô thứ $i$, ta có 2 cách là đặt lát gạch màu đen hoặc màu trắng.

**Trường hợp 1: Đặt lát gạch màu đen ở ô thứ $i$**

Ta có thể lát thêm 1 ô màu đen vào các cấu hình của $dp_0(i - 1)$. Do $dp_0(i - 1)$ đã gồm các cấu hình thỏa rồi và việc thêm $1$ ô đen vào cuối cấu hình chỉ tạo ra dãy gồm $1$ ô đen liên tiếp nên chắc chắn các cấu hình mới này vẫn thỏa điều kiện. Như vậy, $dp_1(i) = dp_0(i - 1)$ $(1)$.

Ta đã có $dp_1(i - 1)$ là số cách lát thỏa yêu cầu cho $i - 1$ ô đầu. Tiếp theo, ta sẽ lát tiếp 1 viên gạch màu đen vào các cách ở $dp_1(i - 1)$ và thế là ta đã có $i$ ô được lát.

Tuy nhiên, $i$ ô này đang gặp vấn đề. Ở $i − 1$ ô đầu, ta có tối đa $k$ ô liên tiếp cùng màu đen (ta chỉ xét các ô màu đen liên tiếp ở cuối các cấu hình của $i − 1$ ô đầu do các dãy ô đen liên tiếp trước đó đều đã cố định và ô màu đen thứ $i$ này không tác động đến). Khi lát ô màu đen vào ô $i$, ta lại có tối đa $k + 1$ ô liên tiếp màu đen và điều này không thỏa yêu cầu. Do đó, ta cần loại các cấu hình này ra.

Cụ thể, các cấu hình cần bị loại có dạng $\{x_1,x_2,...,x_{i - k - 1} = 0,1,1,...,x_i = 1\}$ (có $k + 1$ số 1 tương ứng với $k + 1$ ô đen). Do $k + 1$ ô cuối cùng của cấu hình đã cố định là đen rồi nên số lượng cấu hình gồm $i - k + 1$ ô đầu tiên thỏa yêu cầu. Nói cách khác, số lượng ấy bằng $dp_0(i - k - 1)$. Như vậy, $dp_1(i) = dp_1(i - 1) - dp_0(i - k - 1)$ $(2)$.

Ta cũng có trường hợp ngoại lệ không cần bỏ các cấu hình sai ra, đó là khi $i \le k$ vì khi này không có đủ $k + 1$ ô liên tiếp.

Từ $(1),(2)$, ta có:

==$dp_1(i) = dp_0(i - 1) + dp_1(i - 1) - dp_0(i - k - 1)$ $($ mod $10^9 + 7)$==

**Trường hợp 2: Đặt lát gạch màu trắng ở ô thứ $i$**

Nếu ô thứ $i$ là một trong các ô bắt buộc là màu đen thì $dp_0(i) = 0$.

Ngược lại, ta tính $dp_0(i)$ tương tự $dp_1(i)$:

==$dp_0(i) = dp_1(i - 1) + dp_0(i - 1) - dp_1(i - k - 1)$ $($ mod $10^9 + 7)$==

Tuy nhiên, ta sẽ xét trường hợp ngoại lệ không cần loại cấu hình sai hơi khác.

Gọi $l$ là vị trí lớn nhất trước $i$ mà ở ô thứ $l$, ta bắt buộc lát màu đen, nếu không có thì $l = 0$. Ta đang bỏ ra các cầu hình có $k + 1$ ô cuối cùng màu trắng mà nếu $i - l \le k$ thì không thể tạo đủ $k + 1$ ô cuối cùng màu trắng được. Do đó khi $i - l \le k$ thì ta không cần trừ $dp_1(i - k - 1)$

**Trạng thái cơ sở** $(i = 1)$

Ở ô đầu tiên thì nếu $a_1 = 1$: $dp_1(i) = 1$, $dp_0(i) = 0$. Ngược lại thì cả $2$ giá trị trên đều bằng $1$.

Đáp án của bài toán sẽ là $dp_0(n) + dp_1(n)$ $($ mod $10^9 + 7)$

#include <bits/stdc++.h>

using namespace std;

const int maxN = 2 * 1e5 + 17;
const long long MOD = 1e9 + 7;

int n,m,k;
int a[maxN];
long long dp[2][maxN];
 
void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + m);
 
    int pos = 1, l = 0;
    dp[1][0] = dp[0][0] = 1;
    if (a[pos] == 1)
    {
        dp[0][1] = 0;
        dp[1][1] = 1;
        ++pos;
    }
    else dp[1][1] = dp[0][1] = 1;
 
    for (int i = 2; i <= n; ++i)
    {
        //Xử lý trường hợp khi ô i là đen
        dp[1][i] = (dp[1][i - 1] + dp[0][i - 1]) % MOD;
        if (i > k) dp[1][i] = (dp[1][i] - dp[0][i - k - 1] + MOD) % MOD;
        
        //Xử lý trường hợp khi ô i là trắng
        if (a[pos] == i)
        {
            ++pos;
            dp[0][i] = 0;
            l = i;
        }
        else
        {
            dp[0][i] = (dp[1][i - 1] + dp[0][i - 1]) % MOD;
            if (i - l > k)
            {
                dp[0][i] = (dp[0][i] - dp[1][l] + MOD) % MOD;
                ++l;
            }
        }
    }
    
    cout << (dp[0][n] + dp[1][n]) % MOD;
    
    return;
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    freopen("WHITEBLACK.inp","r",stdin);
    freopen("WHITEBLACK.out","w",stdout);
    
    solve();
 
    return 0;
}