# Lời giải đề chọn đội tuyển PTNK 2024
----
Link đề: https://drive.google.com/drive/folders/1MSBBUs9WVG4DpXiS7Hq77GH9yaXdg6i7
# Bài 1.
Chứng minh được đường đi tối ưu là đi theo đường chéo.
Đi từ (1, 1) -> (1, 2) -> (2, 2) -> ... -> (n, n).
Trong phòng thi mình dùng cách sinh test để kiểm tra
Vậy giá trị lớn nhất với n là:
n - 1 + 1 * 1 + 2 * 2 + .. n * n
<=> n - 1 + n * (n + 1) * (2n + 1) / 6 (Tự chứng minh).
Đến đây chỉ cần chặt nhị phân hoặc toán để tìm n lớn nhất thỏa.

# Bài 2.
Chặt nhị phân đáp án.
Trong hàm check giá trị mid ta có mảng c.
c[i] là số lượng cây cao hơn/bằng mid nếu ta tưới nước ở i.
Nhắc lại công thức:
Nếu ta tưới ở p, h[i + p] += (b + r * i) với 0 <= i < m.
Do b, r không âm, nếu tưới nước ô p làm cây j nào đó đạt chiều cao lớn hơn mid. thì tưới ô p - 1 cũng vậy (nếu trong tầm tăng trưởng).
Duyệt qua các cây, ta có thể dùng toán hoặc chặt nhị phân xác định khoảng tưới làm cây đang xét lớn hơn mid. Cập nhật mảng hiệu

# Bài 3.
Quy hoạch động trên cây.
dp[u][i][cnt] là xét tới subtree u. dist(j, u) <= i với j thuộc subtree u và có cnt cạnh kề u là cao cấp.
Xét trường hợp nâng cấp cạnh u, v khi merge 2 subtree u, v lại.
Xem code để hiểu chi tiết cụ thể
Tác giả chỉ viết công thức, việc ra tư duy ra công thức không đề cập đến

# Bài 4.
Đây là câu đề không viết rõ giới hạn của k lúc thi.
Nguồn đề là: subtask1 bài 3 siêu cúp olp sinh viên 2023.
Theo đề(và bộ test thầy) k <= 50. tuy nhiên vẫn đề cập cách giải với k <= 250.
Quy hoạch động:
Sinh ra tập các tổng có thể tạo ra(tối đa n * (n + 1) / 2 tổng).
Sử dụng hai con trỏ xác định tổng min, max.
Với mỗi cặp tổng min, max, ta quy hoạch động để xác định có
thể chia được thành k nhóm.
Độ phức tạp O(n * (n + 1) / 2 * n * k).

# Bài 5.
Bài này đề ghi 2e5 thành 2e6.
Có không quá logmax(bi) * m giá trị OR đoạn phân biệt.
Có không quá logmax(ai) * n giá trị AND đoạn phân biệt.
Tạp mảng bool đánh dấu x có phải là OR của 1 đoạn nào đó trong b
Tìm được các tuple i, l, r, val mang ý nghĩa:
AND(i, l) = AND(i,l + 1) = .. = AND(i, r) = val.
Nếu ok[val] == 1. Ta lưu lại i, l, r, sort theo i
Với mỗi truy vấn lưu lại l, r, id, sort theo l.
Dùng 2 con trỏ.
Xét tới tuple i, l, r. Lazy update đoạn l, r lên 1.
Xét tới truy vấn l, r, id, đã update các tuple có i >= l. res[id] += get(l, r);

# Bài 6.

# Code
# Bài 1.
Không có đâu lêu lêu :33

# Bài 2.

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

#define int long long

const int maxn = 5e5 + 5;
int n, k, m, b, r;

int h[maxn];

bool check(int mid){
    vector<int> pref(n + 5);

    for(int i = 1; i <= n; i++){
        if(r == 0){
            if(h[i] >= mid){
                pref[1]++;
                pref[n + 1]--;
            }
            else if(h[i] + b >= mid){
                pref[max(0LL, i - m + 1)]++;
                pref[i + 1]--;
            }
            continue;
        }

        int minj = (mid - b - h[i] - 1) / r + (mid - b - h[i] - 1 >= 0 ? 1 : 0);
        minj = max(minj, 0LL);

        if(h[i] >= mid){
            pref[1]++;
            pref[n + 1]--;
        }
        else if(0 <= minj && minj < m){
            pref[max(0LL, i - m + 1)]++;
            pref[max(0LL, i - minj) + 1]--;
        }
    }

    for(int i = 1; i <= n - m + 1; i++){
        pref[i] += pref[i - 1];
        if(pref[i] >= k) return true;
    }

    return false;
}
void solve(){
    cin >> n >> k >> m >> b >> r;

    for(int i = 1; i <= n; i++) cin >> h[i];

    int l = 0, r = 1e15, ans;
    while(l <= r){
        int mid = (l + r) / 2;

        if(check(mid)){
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }

    cout << ans;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    freopen("FERTILIZE.INP", "r", stdin);
    freopen("FERTILIZE.OUT", "w", stdout);

    solve();
}

# Bài 3.

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

#define int long long

const int maxn = 1e5 + 5, mod = 1e9 + 7;

int n, k, lim;
vector<int> adj[maxn];
int f[maxn][20][6];

void dfs(int u, int p) {
    for(int i = 0; i <= lim; i++) f[u][i][0] = 1;

    for(int v: adj[u]){
        if(v == p) continue;
        dfs(v, u);

        for(int cnt = k; cnt >= 0; cnt--){
            for(int i = 0; i <= lim; i++){
                int s = 0;
                //không thêm cạnh
                if(i){
                    for(int j = 0; j <= k; j++) s = (s + f[v][i - 1][j]) % mod;
                }
                (f[u][i][cnt] *= s) %= mod;

                if(cnt > 0){//thêm cạnh. chỉ xét tới k - 1 ở v. 
                    //vì khi nối cũng tăng số lượng dây nối ở v lên 1
                    int s1 = 0;
                    for(int j = 0; j <= k - 1; j++) s1 = (s1 + f[v][i][j]) % mod;
                    f[u][i][cnt] += f[u][i][cnt - 1] * s1 % mod;
                    f[u][i][cnt] %= mod;
                }
            }
        }
    }
}

void solve(){
    cin >> n >> k;

    for(int i = 1; i <= n - 1; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    lim = __lg(n);
    dfs(1, 0);

    int ans = 0;
    for(int i = 0; i <= k; i++) ans = (ans + f[1][lim][i]) % mod;

    cout << ans;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    freopen("SPEEDUP.INP", "r", stdin);
    freopen("SPEEDUP.OUT", "w", stdout);

    solve();
}

# Bài 4
Đây là code sử dụng tham lam + tối ưu.
Lưu lại mọi cặp min max không bao nhau với mọi dp[i][j].
Vẫn chưa tính được độ phức tạp cụ thể nhưng chưa tìm được counter test

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

#define int long long
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    freopen("GIFTS.INP", "r", stdin);
    freopen("GIFTS.OUT", "w", stdout);
    
    int n, k; cin >> n >> k;
    vector<int> a(n), pre(n + 1);

    for(int i = 0; i < n; i++){
        cin >> a[i];
        pre[i + 1] = pre[i] + a[i];
    }

    vector<vector<vector<pair<int, int>>>> dp(n + 1, vector<vector<pair<int, int>>>(k + 1));
    for(int i = 1; i <= n; i++) dp[i][1].push_back({pre[i], pre[i]});
    for(int j = 2; j <= k; j++){
        for(int i = j; i <= n; i++){
            vector<pair<int, int>> cur;
            for(int l = j - 1; l < i; l++){
                int sum = pre[i] - pre[l];
                for(auto p: dp[l][j - 1]) cur.push_back({min(p.first, sum), max(p.second, sum)});
            }
            vector<pair<int, int>> pruned;
            for(auto p: cur){
                bool dominated = false;
                for(auto q: pruned){
                    if(p.first <= q.first && q.second <= p.second){
                        dominated = true;
                        break;
                    }
                }
                if(!dominated){
                    vector<pair<int, int>> c;
                    for(auto [x, y]: pruned){
                        if(x <= p.first && p.second <= y) continue;
                        c.push_back({x, y});
                    }
                    c.push_back(p);
                    pruned = c;
                }
            }
            swap(dp[i][j], pruned);
        }
    }
    int ans = LLONG_MAX;
    for(auto [x, y]: dp[n][k]) ans = min(ans, y - x);
    cout << ans;
}

Code quy hoạch động
Dù đã tối ưu rất nhiều nhưng code vẫn chạy lên tới 1.6s

#include <bits/stdc++.h>
using namespace std;
const int N = 300 + 9, K = 52;

int n, k, ps[N], sum[N];
bool f[K][N];

inline bool ok(int mn, int mx){
	memset(f, 0, sizeof(f));
	for(int i = 1; i <= n; i++) f[1][i] = (mn[i] <= ps[i] && ps[i] <= mx);
	sum[0] = 0;
	for (int i = 2; i <= k; i++){
		for (int j = 1; j <= n; j++) sum[j] = sum[j - 1] + f[i - 1][j];
		int be = 1, en = 0;
		if(sum[n] == 0) break;
		for(int j = 1; j <= n; j++){
			if(ps[j] < mn) continue;
			while(en < j && ps[j] - ps[en] >= mn) en++;
			while(be <= n && ps[j] - ps[be] > mx) be++;
			f[i][j] = sum[en - 1] > sum[be - 1];
		}
	}
	return f[k][n];
}

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

        freopen("GIFTS.INP", "r", stdin);
        freopen("GIFTS.OUT", "w", stdout);
    
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		int x; cin >> x;
		ps[i] = ps[i - 1] + x;
	}

	vector<int> vec;
	for(int i = 1; i <= n; i++) for(int j = i; j <= n; j++) vec.push_back(ps[j] - ps[i - 1]);
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin (), vec.end()), vec.end());

	int r = 0;
	int res = 1e18 + 9;
	for(int i = 0; i < vec.size(); i++){
		while(r < vec.size() && ok(vec[i], vec[r]) == 0) r++;
		if(r == vec.size()) break;
		res = min(res, vec[r] - vec[i]);
	}
	cout << res;
    return 0;
}

Cuối cùng, với những ai thắc mắc nếu k <= n <= 250 thì hướng giải là gì.
dpmn[i] và dpmx[i] là xét tới vị trí i và số lượng đoạn con ít nhất/nhiều nhất được tách ra là bao nhiêu thỏa mỗi tổng đoạn đều vẫn nằm trong khoảng [mn, mx] đang xét.
Độ phức tạp hàm check từ O(n * k) thành O(n * log2(n)).
Do gọi segment tree nhiều lần nên phải code 2 * n mới pass được 1s

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

const int INF = 1e9;

struct MinSegTree{
    int size;
    vector<int> tree;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size, INF);
    }

    void update(int pos, int val) {
        pos += size;
        tree[pos] = min(tree[pos], val);
        for (pos /= 2; pos >= 1; pos /= 2) {
            tree[pos] = min(tree[pos * 2], tree[pos * 2 + 1]);
        }
    }
    
    int query(int l, int r){
        l += size;
        r += size;
        int res = INF;
        while (l < r) {
            if(l % 2 == 1) res = min(res, tree[l++]);
            if(r % 2 == 1) res = min(res, tree[--r]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
} stmn;

struct MaxSegTree{
    int size;
    vector<int> tree;

    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        tree.assign(2 * size, -INF);
    }
    
    void update(int pos, int val) {
        pos += size;
        tree[pos] = max(tree[pos], val);
        for (pos /= 2; pos >= 1; pos /= 2) {
            tree[pos] = max(tree[pos * 2], tree[pos * 2 + 1]);
        }
    }
    
    int query(int l, int r){
        l += size;
        r += size;
        int res = -INF;
        while(l < r) {
            if(l % 2 == 1) res = max(res, tree[l++]);
            if(r % 2 == 1) res = max(res, tree[--r]);
            l /= 2;
            r /= 2;
        }
        return res;
    }
} stmx;

const int maxn = 252;
int pre[maxn];
int n, k;

vector<int> compress; 
int get(int val){
    return lower_bound(compress.begin(), compress.end(), val) - compress.begin();
}

inline bool check(int mn, int mx){
    vector<int> dpmn(n + 1, INF), dpmx(n + 1, -INF);
    
    stmn.init(compress.size());
    stmx.init(compress.size());
    stmn.update(0, 0);
    stmx.update(0, 0);

    for(int i = 1; i <= n; i++){
        int L = get(pre[i] - mx);
        int R = upper_bound(compress.begin(), compress.end(), pre[i] - mn) - compress.begin();
        
        int min_prev = stmn.query(L, R);
        
        if(min_prev != INF){
            int max_prev = stmx.query(L, R);
            dpmn[i] = min_prev + 1;
            dpmx[i] = max_prev + 1;

            stmn.update(i, dpmn[i]);
            stmx.update(i, dpmx[i]);
            if(dpmn[i] > k) return false;
        }
    }

    return dpmn[n] <= k && k <= dpmx[n];
}

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

    freopen("GIFTS.INP", "r", stdin);
    freopen("GIFTS.OUT", "w", stdout);
    cin >> n >> k;

    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        pre[i] = pre[i - 1] + x;
    }

    vector<int> vec;
    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++) vec.push_back(pre[j] - pre[i - 1]);
    }

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

    for(int i = 0; i <= n; i++) compress.push_back(pre[i]);
    
    int ans = vec.back() - vec.front(), j = 0;
    for(int i = 0; i < vec.size(); i++){
        while(j < vec.size() && !check(vec[i], vec[j])) j++;
        if(j == vec.size()) break;
        ans = min(ans, vec[j] - vec[i]);
    }

    cout << ans;
    return 0;
}

# Bài 5.

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

const int maxn = 2e6 + 5;

long long st[4 * maxn], lazy[4 * maxn];
vector<pair<int, int>> range[maxn];
void down(int id, int l, int r){
    int mid = (l + r) / 2;
    st[id * 2] += lazy[id] * (mid - l + 1);
    st[id * 2 + 1] += lazy[id] * (r - mid);
    lazy[id * 2] += lazy[id];
    lazy[id * 2 + 1] += lazy[id];
    lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v){
    if(l > v || r < u) return;
    if(u <= l && r <= v){
        st[id] += (r - l + 1);
        lazy[id] += 1;
        return;
    }
 
    down(id, l, r);
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v);
    update(id * 2 + 1, mid + 1, r, u, v);
    st[id] = (st[id * 2] + st[id * 2 + 1]);
}
 
long long get(int id, int l, int r, int u, int v){
    if(l > v || r < u) return 0;
    if(u <= l && r <= v) return st[id];
 
    down(id, l, r);
 
    int mid = (l + r) / 2;
    return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}

int a[maxn], b[maxn];
int nxtpos[maxn][22], nxtpos2[maxn][22];
int beauty[maxn];

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

    freopen("AND2OR.INP", "r", stdin);
    freopen("AND2OR.OUT", "w", stdout);
    
    int n, m, q; cin >> n >> m >> q;

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

    //tim tat ca so dep
    for(int bit = 21; bit >= 0; bit--) nxtpos[m + 1][bit] = m + 1;
    for(int i = m; i >= 1; i--){
        for(int bit = 21; bit >= 0; bit--) nxtpos[i][bit] = (b[i] & (1 << bit)) ? i : nxtpos[i + 1][bit];
    }

    for(int bit = 21; bit >= 0; bit--) nxtpos2[n + 1][bit] = n + 1;
    for(int i = n; i >= 1; i--){
        for(int bit = 21; bit >= 0; bit--) nxtpos2[i][bit] = ((a[i] & (1 << bit)) == 0) ? i : nxtpos2[i + 1][bit];
    }

    for(int i = 1; i <= m; i++){
        int cur = b[i], curpos = i;
        beauty[cur] = 1;
        while(curpos <= m){
            int nxt = m + 1;
            for(int bit = 0; bit <= 21; bit++){
                if((cur & (1 << bit)) == 0) nxt = min(nxt, nxtpos[curpos][bit]);
            }

            if(nxt <= m) cur |= b[nxt];
            beauty[cur] = 1;
            curpos = nxt; 
        }
    }

    for(int i = 1; i <= n; i++){
        int cur = a[i], curpos = i;
        while(curpos <= n){
            int nxt = n + 1;
            for(int bit = 0; bit <= 21; bit++){
                if(cur & (1 << bit)) nxt = min(nxt, nxtpos2[curpos][bit]);
            }

            if(beauty[cur]) range[i].push_back({curpos, nxt - 1});
            if(nxt <= n) cur &= a[nxt];
            curpos = nxt;
        }
    }

    vector<long long> res(q + 1);
    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        range[l].push_back({r, -i});
    }

    for(int i = n; i >= 1; i--){
        for(auto [l, r]: range[i]){
            if(r < 0) res[-r] = get(1, 1, n, 1, l);
            else update(1, 1, n, l, r);
        }
    }

    for(int i = 1; i <= q; i++) cout << res[i] << "\n";
    return 0;
}