VOJ - DIVSEQQ

Source: DIVSEQQ
Tags: Dynamic Programming, Data Structures

Problem:
Cho một dãy A gồm N phần tử, thực hiện Q truy vấn dạng (u, v) như sau:
- Tìm vị trí e nhỏ nhất sao cho dãy con từ e đến u có thể được chia thành x đoạn con (x ≤ v) với tổng mỗi đoạn con không vượt quá M.
N, Q ≤ 1e5.
M ≤ 1e9.
0 ≤ A[i] ≤ M.
0 < u ≤ N.
0 < v ≤ 1e9.

Ví dụ:
Input:
5 2 8
1 2 3 4 5
4 2
5 2

Output:
1
3

Explanation:
Từ 1 đến 4 có thể chia thành các đoạn con sau (1, 2), (3, 4).
Từ 3 đến 5 có thể chia thành các đoạn con sau (3, 4), (5).

Solution:
Trong subtask 1 của bài toán (coi trong link đề gốc có giới hạn subtask 1), với mỗi truy vấn ta có thể binary search vị trí của e rồi duyệt DP kiểm tra rất đơn giản. Vậy DP để kiểm tra ở đây như nào?
Gọi F[i] là số đoạn ít nhất mà vẫn thỏa điều kiện tổng mỗi đoạn ≤ M, ta muốn ở đây là ít đoạn nhất để đảm bảo điều kiện x ≤ v. Dễ dàng nhận thấy DP cộng chút greedy trong đây ra được công thức
F[i] = F[j] + 1, với j là vị trí xa nhất mà A[j + 1] + A[j + 2] + ... + A[i] ≤ M.
Vì ta muốn ít đoạn nhất nên ta greedy lấy nhiều phần tử nhất có thể rồi cộng cho cách chia dãy trước đấy. Muốn tìm được j thì đơn giản, 2 pointers hoặc binary search đều có thể sử dụng được. Cơ sở là F[e] = 1, F[i] = 0 (với i < e).
Rồi đấy là subtask 1, ta có thể dựa vào điều gì để tối ưu? Để ý một điều rằng, với công thức DP như trên, mỗi thằng i sẽ phụ thuộc vào một thằng j nhất định. Nếu F[u] ≤ v, rõ ràng đáp án là 1. Nếu không, F[u] cần giảm một lượng là F[u] - v.
Lập mảng F theo test đề bài:
A: 1 2 3 4 5
F: 1 1 1 2 3
Nếu biểu diễn mối quan hệ giữa các phần tử lại ta có thể dựng thành một đồ thị như sau

Để giảm F[u], vậy ta sẽ tìm một đỉnh tổ tiên i của u có F[i] = F[u] - v và chọn nó làm gốc, vậy lúc này F[i] = 0 và tương tự tất cả những đỉnh con của nó sẽ được giảm một lượng là F[u] - v. Những đỉnh j còn lại sẽ đảm bảo luôn có F[j] ≤ F[u] (rõ ràng vì mảng F luôn tăng dần) và luôn tìm được đỉnh mới để nối vào tương ứng. Vì ta chỉ cần biết đỉnh e của dãy là gì nên chỉ cần in ra <chỉ số đỉnh gốc> + 1 là được. Vậy tìm đỉnh i đấy như thế nào? Chúng ta có thể sử dụng thủ thuật quen thuộc của LCA là dùng Sparse Table để tìm đỉnh tổ tiên thứ v.
Độ phức tạp tạo mảng F O(2N), tạo Sparse Table O(NlogN), tìm đỉnh tổ tiên thứ v O(log(v)), tổng cộng khoảng O(3NlogN + Qlog(v)).

Code:
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int n, q, m, a[100015], f[100015], p[20][100015];

int main() {
    cin >> n >> q >> m;
    for (int i = 1, j = 1, s = 0; i <= n; i++) {
        cin >> a[i]; s += a[i];
        while (s > m) s -= a[j++];
        f[i] = f[j - 1] + 1;
        p[0][i] = j - 1;
    }
    for (int i = 1; i <= log2(n); i++)
        for (int j = 1; j <= n; j++)
            p[i][j] = p[i - 1][p[i - 1][j]];
    for (int u, v; q--;) {
        cin >> u >> v;
        if (f[u] <= v) cout << "1\n";
        else {
            int x = f[u] - v;
            for (int i = log2(f[u]); i >= 0; i--)
                if (f[p[i][u]] >= x) u = p[i][u];
            cout << u + 1 << '\n';
        }
    }
}