Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Tiếp nối 03 số đầu tiên, các Coding Challenge #04, #05, #06 và #07 tiếp tục ghi nhận sự ủng hộ nhiệt tình của cộng đồng lập trình thi đấu. Hệ thống đã ghi nhận tổng cộng 2086 lượt nộp bài và ~x~ lời giải được gửi về cho Tạp chí.

Đội ngũ tạp chí VNOI xin gửi lời cảm ơn chân thành đến tất cả các bạn đã tích cực tham gia các Coding Challenge và đóng góp những lời giải vô cùng chất lượng trong thời gian qua!

Coding Challenge #7

Coding Challenge #7 có tên là Tổng mod. Đây là bài toán truy vấn yêu cầu thí sinh phải vận dụng được kỹ thuật đường quét và các cấu trúc dữ liệu cần thiết để xây dựng lời giải. Bài toán Tổng mod đã được 334 thí sinh thử sức và có 10 lời giải xuất sắc đạt được số điểm tối đa.

Để hiểu rõ hơn về lời giải của bài toán, mời các bạn theo dõi 2 lời giải xuất sắc do bạn Nguyễn Hoàng Minh (lời giải 1) và Lê Minh Tuấn (lời giải 2) biên soạn.

Đề bài

Bạn đọc có thể theo dõi đề bài gốc và subtasks tại nền tảng VNOJ. Sau đây là bản tóm tắt của đề bài.

Cho dãy ~a~ gồm ~n~ phần tử và ~q~ truy vấn có dạng:

• Cho hai số nguyên ~l, r~, tính tổng sau: ~\sum_{i=l}^r a_i \bmod (i - l + 1)~</cetner>

Giới hạn:

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq a_i \leq 2 \cdot 10^5~

Lời giải 1

Subtask 1

Giới hạn: ~n, q \le 7000~

Ý Tưởng

• Ta đặt tổng cần tìm cho mỗi truy vấn như sau:

• Với giới hạn nhỏ của ~n~ và ~q~ được cho, subtask 1 cho phép chúng ta có thể xử lý từng truy vấn ~(l, r)~ và tính ~S(l, r)~ bằng cách duyệt qua các vị trí từ ~l~ tới ~r~ và trực tiếp tính ~S(l, r)~ theo định nghĩa như trên.

Độ Phức Tạp

• Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O(n \cdot q)~ bởi ta sẽ duyệt qua ~O(q)~ truy vấn và với mỗi truy vấn, ta duyệt qua ~O(n)~ vị trí để tính tổng ~S~. Với giới hạn thời gian được cho (~2.5~ giây), chương trình được cài đặt theo ý tưởng nêu trên có thể chạy trong thời gian cho phép.
• Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(n)~ bởi ta cần lưu ~O(n)~ phần tử của mảng ~a~ được cho.

Code Minh Họa

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

constexpr int MAX_N = 200'005, MAX_Q = 200'005;

int n, q, a[MAX_N];

namespace FirstSubtask {

    int computeValue(const int l, const int r) {
        int result = 0;
        for (int i = l, h = 1; i <= r; ++i, ++h)
            result += a[i] % h;
        return result;
    }

    void solve() {
        for (int i = 1, l = 1, r = n; i <= q; ++i) {
            cin >> l >> r;
            cout << computeValue(l, r) << '\n';
        }
    }

}

void input() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    FirstSubtask::solve();

    return 0;
}

Subtask 2

Giới hạn: ~a_i \le 200~

Ý Tưởng

• Ta có thể viết lại công thức tính tổng cần tìm như sau:

• Ta nhận thấy rằng với hai số nguyên dương ~x~ và ~y~ bất kì, nếu ~x < y~, ta có: ~x \bmod y = x~.
• Nếu ta đặt ~A~ là giá trị lớn nhất mà một phần tử của mảng ~a~ có thể có (~A = 200~ trong subtask 2), với một truy vấn ~(l, r)~ mà ~r - l + 1 > A~, ta có:

Dựa vào tính chất đề cập được nêu trên, ta có:

• Ta nhận thấy rằng, việc tính thành phần tổng mà không phải xét tới phép chia lấy dư tương đương với việc tính tổng các phẩn tử của một mảng con liên tiếp. Vì dãy số ~a~ không thay đổi trong suốt quá trình trả lời truy vấn, ta có thể tính thành phần này bằng cách dùng mảng cộng dồn. Cụ thể hơn, nếu ta đặt ~P[x] = \sum_{i = 1}^{x}a[i]~ là tổng các phần tử của dãy số ~a~ từ vị trí ~1~ đến vị trí ~x~, ta có:

• Mặt khác, giới hạn ~A~ của subtask 2 cho phép ta tính thành phần phải sử dụng đến phép chia lấy dư (thành phần ~\sum_{m = 1}^{A}(a[l + m - 1] \bmod m)~ trong công thức trên) bằng cách duyệt qua từng vị trí như trong subtask 1. Tương tự, nếu ~r - l + 1 \leq A~, ta có thể tính tổng ~S(l, r)~ như trong subtask 1.

Độ Phức Tạp

• Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O(n + q \cdot A)~ bởi:
  • Ta cần đọc dữ liệu dãy số ~a~ với ~O(n)~ phần tử và có thể tính mảng cộng dồn với độ phức tạp ~O(n)~.
  • Với mỗi truy vấn ~(l, r)~, vì tổng các phần tử liên tiếp có thể được tính trong ~O(1)~ sau khi đã xây dựng mảng cộng dồn và ta có thể chỉ cần duyệt thêm qua tối đa ~O(A)~ vị trí để thực hiện việc tính tổng ~S(l, r)~, việc xử lý mỗi truy vấn có thể được thực hiện với độ phức tạp ~O(A)~. Vì ta có ~O(q)~ truy vấn, việc xử lý hết tất cả truy vấn có thể thực hiện với độ phức tạp ~O(q \cdot A)~.
• Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(n)~ bởi ta có thể chỉ cần lưu thêm mảng cộng dồn với ~O(n)~ phần tử so với subtask 1.

Code Minh Họa

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

constexpr int MAX_N = 200'005, MAX_Q = 200'005;

int n, q, a[MAX_N];

namespace SecondSubtask {

    constexpr int MAX_A = 200;

    void solve() {
        int prefixSums[n + 1]{}, result = 0;

        for (int i = 1; i <= n; ++i)
            prefixSums[i] = prefixSums[i - 1] + a[i];

        for (int i = 1, z = 0, h = 0, l = 1, r = n; i <= q; ++i) {
            result = 0;
            cin >> l >> r;
            for (z = l, h = 1; z <= r; ++z, ++h) {
                if (h > MAX_A) {
                    result += prefixSums[r] - prefixSums[z - 1];
                    break;
                }
                result += a[z] % h;
            }
            cout << result << '\n';
        }
    }

}

void input() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    SecondSubtask::solve();

    return 0;
}

Subtask 3

Giới hạn: ~r = n~

Ý Tưởng

• Vì biên trái của mọi truy vấn trong subtask 3 luôn nằm ở vị trí cuối cùng, vỡi mỗi vị trí ~i~, phần tử ~a[i]~ sẽ có đóng góp vào tổng ~S(l, r)~ nếu ~l \leq i~ (~r = n~). Để giải quyết subtask này, ta có thể phân tích xem, với một vị trí ~i~, ~a[i]~ có đóng góp như thế nào tới các tổng ~S(j, n)~ với ~1 \leq j \leq n~.
• Nếu ~x~ và ~y~ là hai số nguyên dương, ta có:

Áp dụng điều này vào ~S(l, r)~, ta có:

Tương tự như subtask 2, thành phần ~\sum_{i = l}^{r}a[i]~ có thể được tính hiệu quả bằng cách sử dụng mảng cộng dồn. Bài toán con còn lại ta phải giải quyết là làm sao để tính thành phần ~\sum_{m = 1}^{r - l + 1} \left(m \cdot \left\lfloor \frac{a[i + m - 1]}{m} \right\rfloor \right)~ một cách hiệu quả.

• Để dễ mô tả phần còn lại của ý tưởng, ta sẽ đặt ~b[i][j] = \left(j - i + 1\right) \left\lfloor \frac{a[i]}{j - i + 1} \right\rfloor~ với ~i, j~ là hai số tự nhiên sao cho ~1 \leq i \leq j \leq n~. Đồng thời, ta đặt ~B[i][j] = \sum_{z = i}^{j}b[i][z]~. Như vậy, với một truy vấn ~(l, r)~, ta cần xác định giá trị ~B[l][r]~.
• Ta nhận thấy rằng với một số nguyên dương cố định ~x~ và một số nguyên dương ~y~, giá trị ~\left\lfloor \frac{x}{y} \right\rfloor~ chỉ có thể có tối đa ~O(\sqrt x)~ khác nhau.

Dựa trên điều này, ta nhận thấy rằng với một vị trí ~i~, ta có thể phân các vị trí từ ~1~ đến ~i - 1~ thành ~O\left(\sqrt {a[i]}\right)~ nhóm gồm các phân tử liên tiếp trong ~b~ sao cho hiệu giữa hai phần tử liên tiếp là như nhau.

• Vì ta không phải thực hiện các truy vấn cập nhật online, ta có thể tính giá trị ~s~ bằng một cách xử lý offline với mảng hiệu:
  • Ta đặt ~D_2[i]~ là giá trị của mảng hiệu đại diện tổng hiệu các step của các truy vấn cập nhật có bao gồm vị trí ~i~.
  • Ta đặt ~D_1[i]~ là tổng các thay đổi cho các truy vấn bắt đầu hoặc kết thúc tại ~i~.

Độ Phức Tạp

• Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian ~O\left(q + n \cdot \sqrt{A}\right)~ với ~A~ là giá trị lớn nhất của mảng ~a~.
  • Ta cần duyệt qua ~O(n)~ vị trí và với mỗi vị trí, ta cần duyệt qua ~O\left(\sqrt{a}\right)~ truy vấn cập nhật. Việc cập nhật hai ~D_1~ và ~D_2~ nêu trên cho mỗi truy vấn có độ phức tạp ~O(1)~.
  • Ta cần duyệt qua ~O(n)~ vị trí để tính mảng ~s~ với mỗi vị trí có thể được xử lý trong ~O(1)~.
  • Ta cần duyệt qua ~O(q)~ truy vấn để xử lý các truy vấn. Mỗi truy vấn có thể được xử lý trong ~O(1)~ sau khi đã thực tính mảng ~s~ trên.
• Xét với độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(n)~ bởi ta có thể chỉ cần lưu thêm mảng hiệu với ~O(n)~ phần tử so với subtask 2.

Code Minh Họa

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

constexpr int MAX_N = 200'005, MAX_Q = 200'005;

int n, q, a[MAX_N];

namespace ThirdSubtask {

    void solve() {
        long long d[n + 1][2]{}, results[n + 1]{}, sum = 0, change = 0;

        for (int i = n, l = 1, r = 1, j = 1, delta = 0, value = 0; i >= 1; --i) {
            value = a[i];
            for (l = 1; l <= value; l = r + 1) {
                delta = value / l;
                if (i < l)
                    break;
                j = i - l + 1;
                d[j][0] += delta * (l - 1);
                d[j][1] += delta;
                r = value / delta;
                if (i <= r)
                    break;
                j = i - r;
                d[j][0] -= delta * r;
                d[j][1] -= delta;
            }

            change += d[i][1];
            sum += a[i] - d[i][0] - change;
            results[i] = sum;
        }

        for (int i = 1, l = 1, r = n; i <= q; ++i) {
            cin >> l >> r;
            cout << results[l] << '\n';
        }
    }

}

void input() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    ThirdSubtask::solve();

    return 0;
}

Subtask 4

Giới hạn: ~n, q \le 2 \times 10^5~

Ý Tưởng

• Để mở rộng hướng giải quyết của subtask 3 cho subtask 4, ta nhận thấy rằng để nếu ta đã tính được ~B[l][r]~ quả cho truy vấn ~(l, r)~ và mảng hiệu ~D_1~ và ~D_2~ nếu chỉ xét các vị trí từ ~1~ tới ~r~, ta có thể mở rộng hoặc thu hẹp biên ~l~ và ~r~ như sau:
  • Để xử lý cho truy vấn ~(l - 1, r)~, ta chỉ cần dựa vào ~B[l][r]~, ~D_1[l - 1]~ và ~D_2[l - 1]~ để xác định giá trị ~B[l - 1][r]~ (mảng ~D_1~ và ~D_2~ giữ nguyên).
  • Tương tự, để xử lý cho truy vấn ~(l + 1, r)~, ta chỉ cần dựa vào ~B[l][r]~, ~D_1[l]~ và ~D_2[l]~ để xác định giá trị ~B[l + 1][r]~ (mảng ~D_1~ và ~D_2~ giữ nguyên).
  • Để xử lý cho truy vấn ~(l, r + 1)~, ta có thể tính ~b[l][r + 1]~ để cùng với giá trị ~B[l][r]~ tính giá trị ~B[l][r + 1]~. Đồng thời, để cập nhật mảng ~D_1~ và ~D_2~, ta cần duyệt qua mọi truy vấn cập nhật tạo bởi vị trí ~r + 1~.
  • Để xử lý cho truy vấn ~(l, r - 1)~, ta có thể tính ~b[l][r]~ để cùng với giá trị ~B[l][r]~ tính giá trị ~B[l][r - 1]~. Đồng thời, để cập nhật mảng ~D_1~ và ~D_2~, ta cần duyệt qua mọi truy vấn cập nhật tạo bởi vị trí ~r~.
• Ta nhận thấy rằng trong cả bốn trường hợp nêu trên, việc tính giá trị ~B~ mới có thể được xử lý ~O(1)~. Vì vậy, việc mở rộng hoặc thu hẹp biên biên trái (bởi một đơn vị) có thể được xử lý trong ~O(1)~. Tuy nhiên, việc mở rộng hoặc thu hẹp biên phải (bởi một đơn vị) có thể yêu cầu độ phức tạp ~O\left(\sqrt{A}\right)~ bởi ta sẽ cập nhật ~D_1~ và ~D_2~ theo cách trên.
• Nếu ta giả định việc duyệt qua các thao tác cập nhật là các thao tác tối thiểu, ta có thể xem xét áp dụng thuật toán Mo bởi:
  • Độ phức tạp thời gian sẽ là ~O\left(n \sqrt{A} + (n + q) \sqrt{n} Z \right)~ với ~O(Z)~ là độ phức tạp của việc mở rộng hoặc thu hẹp một trong hai biên. Vì vậy, nếu ta xử lý việc thay đổi biên đủ hiệu quả, thời gian chạy của chương trình vẫn có thể trong giới hạn cho phép.
  • Ta có thể trả lời các truy vấn một cách offline.
  • Việc gộp hai cấu trúc dữ liệu (giá trị ~B~ của biên đang xét, mảng ~D_1~ và ~D_2~ được định nghĩa như trên) có thể phức tạp, không đáp giới hạn được đề ra.
• Một cách sắp xếp xử lý truy vấn để có thể áp dụng thuật toán Mo là ta sắp xếp theo chỉ số block của biên ~l~ giảm dần và biên ~r~ giảm dần nếu chỉ số block của biên ~l~ là giống nhau. Cách sắp xếp này có thể giúp ý tưởng có độ phức tạp trong giới hạn cho phép bởi giữa hai truy vấn có biên phải trong cùng một block:
  • Ta sẽ đi qua tối đa ~O\left(\sqrt{n}\right)~ vị trí khi thay đổi biên trái. Mặt khác, việc cập nhật giá trị ~B~ khi chỉ thay đổi biên phải là ~O(1)~ như đã đề cập trước đó.
  • Khi thay đổi (giảm) biên phải, ta sẽ duyệt qua các truy vấn cập nhật có ít nhất một vị trí nằm trong block đang xét. Độ phức tạp cho một lần giảm biên phải như vậy sẽ là ~O\left(\sqrt A\right)~. Ta có thể đưa ra nhận xét là với một vị trí ~r~, tổng số truy vấn cập nhật ta phải duyệt qua khi giảm ở biên phải đang ở vị trí ~r~ là ~O\left(\sqrt{n \cdot A}\right)~. Tuy nhiên, ta có thể có một nhận xét chặt hơn: số lượng thật sự sẽ là ~O\left(\sqrt{A} + \sqrt{n}\right)~ bởi:
    • Các truy vấn cập nhật cho giá trị ~a[r]~ không có chung vị trí giữa chúng;
    • Ở mỗi block, ta chỉ duyệt qua các truy vấn cập nhật có ít nhất một vị trí trong block như đã đề cập ở trên.

Độ Phức Tạp

• Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O\left(n\sqrt{A} + (n + q)\sqrt{n}\right)~ bởi:
  • Việc sắp xếp ~q~ truy vấn có thể được thực hiện trong ~O(n + q)~ nếu ta dùng thuật toán sắp xếp đếm phân phối (vì đây là thuật toán sắp xếp ổn định, ta có thể sắp xếp các truy vấn theo biên phải ~r~ trước rồi sắp xếp theo vị trí block của biên trái ~l~).
  • Độ phức tạp của bước xử lý chính của thuật toán Mo sẽ là ~O\left(n \sqrt{A} + (n + q)\sqrt{n}\right)~ dựa trên phân tích đề cập trong phần trước:
    • Ta sẽ thay đổi biên trái ~l~ tối đa ~O\left(q \sqrt {n} \right)~ lần khi duyệt hết ~q~ truy vấn và độ phức tạp cho mỗi lần thay đổi là ~O(1)~.
    • Tổng độ phức tạp cho việc thay đổi biên phải ~r~ sau khi duyệt ~q~ truy vấn là ~O\left(n(\sqrt{A} + \sqrt{n})\right)~ vì ta có ~O(n)~ vị trí cho biên phải và tổng phức tạp cho bước xử lý một vị trí biên phải là ~O\left(\sqrt{A} + \sqrt{n}\right)~ như đã đề cập ở trên.
• Về độ phức tạp bộ nhớ, ý tưởng có thể được cài đặt với độ phức tạp ~O(n + q)~ bởi ta có thể chỉ cần lưu thêm các chỉ số của truy vấn với ~O(q)~ phần tử so với subtask 3 để có thể sắp xếp và xử lý theo một thứ tự nhất định.

Code Minh Họa

• Khi cài đặt ý tưởng, chúng ta nên cố gắng tránh sử dụng phép chia nhiều nhất có thể bởi phép chia có thể làm chậm chương trình (nếu số chia không phải là một hằng số có thể xác định khi biên dịch chương trình, phép chia có thời gian thực thi chậm hơn đáng kể so với phép cộng, trừ, hoặc nhân).

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

constexpr int MAX_N = 200'005, MAX_Q = 200'005;

int n, q, a[MAX_N], l[MAX_Q], r[MAX_Q];

namespace FourthSubtask {

    constexpr int BLOCK_SIZE = 447, BLOCK_COUNT = 450;

    long long results[MAX_Q], prefixSums[MAX_N], d[MAX_N][2];
    int queryIndices[MAX_Q], ranges[MAX_N][3];

    void sortQueries() {
        int i = 0, lefts[n + 1]{}, indices[q + 1]{};
        /**
            Sort by ascending L
        **/
        for (i = 1; i <= q; ++i)
            ++lefts[l[i] + 1];
        for (i = 1; i <= n; ++i)
            lefts[i] += lefts[i - 1];
        for (i = 1; i <= q; ++i)
            queryIndices[++lefts[l[i]]] = i;
        /**
            Sort by ascending R
        **/
        for (i = 1; i <= n; ++i)
            lefts[i] = 0;
        for (i = 1; i <= q; ++i)
            ++lefts[r[i] + 1];
        for (i = 1; i <= n; ++i)
            lefts[i] += lefts[i - 1];
        for (i = 1; i <= q; ++i)
            indices[++lefts[r[queryIndices[i]]]] = queryIndices[i];
        /**
            Sort by descending block ID of L
        **/
        for (i = 1; i <= n; ++i)
            lefts[i] = 0;
        for (i = 1; i <= q; ++i)
            ++lefts[n - (l[i] - 1) / BLOCK_SIZE + 1];
        for (i = 1; i <= n; ++i)
            lefts[i] += lefts[i - 1];
        for (i = 1; i <= q; ++i)
            queryIndices[++lefts[n - (l[indices[i]] - 1) / BLOCK_SIZE]] = indices[i];
    }

    void solve() {
        long long sum = 0, change = 0;
        int i = 1;

        sortQueries();

        for (; i <= n; ++i) {
            prefixSums[i] = prefixSums[i - 1] + a[i];
            ranges[i][0] = ranges[i][2] = 1;
            ranges[i][1] = a[i];
        }

        i = 1;

        for (int blockLeft = (n - 1) / BLOCK_SIZE * BLOCK_SIZE + 1, blockRight = n, start = 0, last = 0, left = 0, delta = 0, right = 0, t = 0, value = 0, rangeLeft = 0, rangeRight = 0, queryLeft = 0, queryRight = 0; blockLeft >= 1 && i <= q; blockRight = blockLeft - 1, blockLeft -= BLOCK_SIZE) {
            sum = change = 0;
            start = blockLeft;
            last = start - 1;
            for (; i <= q; ++i) {
                t = queryIndices[i];
                queryLeft = l[t];
                if (queryLeft < blockLeft)
                    break;
                queryRight = r[t];
                while (queryLeft < start) {
                    --start;
                    change += d[start][1];
                    sum += d[start][0] + change;
                }
                for (; start < queryLeft; ++start) {
                    sum -= d[start][0] + change;
                    change -= d[start][1];
                }
                for (queryRight = r[t]; last < queryRight;) {
                    ++last;
                    left = ranges[last][0];
                    value = a[last];
                    if (left > value)
                        continue;
                    delta = ranges[last][1];
                    right = ranges[last][2];
                    while (true) {
                        rangeRight = last - left + 1;
                        if (rangeRight < blockLeft)
                            break;
                        rangeLeft = max(last - right, 0);
                        if (rangeLeft < blockRight) {
                            /**
                                (rangeLeft, rangeRight]
                            **/
                            if (rangeLeft < start && start <= rangeRight) {
                                sum += delta * (last - start + 1);
                                change += delta;
                            }
                            if (rangeRight <= blockRight) {
                                d[rangeRight][0] += delta * (last - rangeRight);
                                d[rangeRight][1] += delta;
                            }
                            if (rangeLeft < blockLeft)
                                break;
                            d[rangeLeft][0] -= delta * (last - rangeLeft);
                            d[rangeLeft][1] -= delta;
                        }
                        left = right + 1;
                        if (left > value)
                            break;
                        delta = value / left;
                        right = value / delta;
                    }
                    ranges[last][0] = left;
                    ranges[last][1] = delta;
                    ranges[last][2] = right;
                }
                results[t] = prefixSums[r[t]] - prefixSums[l[t] - 1] - sum;
            }
        }

        for (i = 1; i <= q; ++i)
            cout << results[i] << '\n';
    }
}

void input() {
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= q; ++i)
        cin >> l[i] >> r[i];
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    FourthSubtask::solve();

    return 0;
}

Lời giải 2

Subtask 1: ~n, q \le 7000~

Ta chỉ cần làm đúng những gì đề bảo. Với mỗi truy vấn, ta duyệt từ ~l~ đến ~r~, và cộng giá trị ~a_i \bmod (i-l+1)~ vào biến kết quả. Độ phức tạp ~\mathcal{O}(q \cdot n)~.

#include <bits/stdc++.h>

using namespace std;

int a[200005];
int n, q;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    int64_t ans = 0;
    for (int i = l; i <= r; i++) {
      ans += a[i] % (i - l + 1);
    }
    cout << ans << '\n';
  }
  return 0;
}

Subtask 2: ~a_i \le 200~

Nhận xét: ~x \bmod y = x~ nếu ~x < y~. Đặt ~k = i - l + 1~ là số chia. Với mỗi truy vấn ~[l, r]~, ta chia làm 2 phần:

• Với ~k \le 200~ (tương ứng với 200 phần tử đầu tiên của đoạn, tức ~i \in [l, \min(r, l+199)]~), ta tính trực tiếp tổng ~a_i \bmod k~ bằng cách duyệt như subtask 1.
• Với ~k > 200~, do ~a_i \le 200~ nên ~a_i < k~, suy ra ~a_i \bmod k = a_i~. Phần này ta có thể tính nhanh bằng prefix sum.

Độ phức tạp: ~\mathcal{O}(q \cdot 200)~. Trong cài đặt mẫu dưới đây, tác giả sử dụng Sparse Table để tìm max đoạn ~[l,r]~ nằm tối ưu thời gian chạy với những test có ~\max a~ nhỏ hơn. Còn trên thực tế, ta duyệt đến ~l+200~ vẫn đủ để qua được subtask này.

#include <bits/stdc++.h>

using namespace std;

template <typename T, typename F>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  vector<int> pref(n);
  for (auto& it : a) {
    cin >> it;
  }
  pref[0] = a[0];
  for (int i = 1; i < n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  auto f = [&](int x, int y) { return max(x, y); };
  SparseTable<int, decltype(f)> st(a, f);
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    int ma = st.get(l, r);
    int64_t ans = 0;
    for (int i = l; i <= min(r, l + ma - 1); i++) {
      ans += a[i] % (i - l + 1);
    }
    if (l + ma <= r) {
      ans += pref[r] - pref[l + ma - 1];
    }
    cout << ans << '\n';
  }
  return 0;
}

Subtask 3: ~r = n~

Trong lời giải sau, đặt ~A = \max(a_i)~. Ta có:

Do đó:

Phần tổng ~a_i~ cố định có thể tính bằng Prefix Sum. Lời giải sau đây chỉ quan tâm đến việc tính tổng ở vế sau (~\sum_{i=l}^{n} (i-l+1) \left\lfloor \frac{a_i}{i-l+1} \right\rfloor~).

Nhận xét:

• Chỉ có tối đa ~2\sqrt{n}~ giá trị ~\lfloor \frac{n}{c} \rfloor~ phân biệt.
  • Nếu ~c \le \sqrt{n}~, rõ ràng số lượng giá trị phân biệt tương ứng với số lượng số ~c~, là ~\sqrt{n}~
  • Nếu ~c > \sqrt{n}~, thì ~\lfloor \frac{n}{c} \rfloor~ chỉ nhận các giá trị nguyên từ ~1~ đến ~\sqrt{n}~.
  • Tổng lại ta có số lượng giá trị phân biệt tối đa là ~2\sqrt{n}~.
• Các giá trị ~c~ có cùng kết quả khi tính ~\lfloor \frac{n}{c} \rfloor~ nằm trên một đoạn liên tiếp của trục số.
  • Điều này là dễ thấy dựa vào tính chất đơn điệu của ~\lfloor \frac{n}{c} \rfloor~.

Từ các nhận xét trên, ta có thể rút ra một cách làm offline cho subtask này. Thay vì duyệt đoạn ~[l,n]~ để trả lời truy vấn, ta duyệt từng phần tử ~a_i~, và xem nó đóng góp bao nhiêu vào kết quả. Nhận thấy ~a_i~ sẽ đóng góp vào các truy vấn ~[l,n]~ với ~l \le i~.

Xét một phần tử ~a_i~, ta duyệt các giá trị ~k = i-l+1~.

• Ta duyệt các đoạn ~[u, v]~ của số chia ~k~ sao cho ~\lfloor \frac{a_i}{k} \rfloor~ có cùng giá trị là ~val~.
  • Từ nhận xét trên, ta thấy phần này chỉ duyệt qua ~2 \sqrt{a_i}~ giá trị khác nhau.
  • Ta có thể duyệt ~u~ tăng dần từ ~1~. Với mỗi ~u~, ta chặt nhị phân tìm ~v~ xa nhất sao cho ~\lfloor \frac{a_i}{u} \rfloor = \lfloor \frac{a_i}{v} \rfloor~. Sau khi tính toán xong, gán ~u \leftarrow v+1~.
  • Tuy nhiên độ phức tạp cho việc trên có thể lên đến ~\mathcal{O}(\sqrt{a_i} \log {a_i})~.
  • Ta có thể tìm ~v~ trong ~\mathcal{O}(1)~ bằng công thức ~v=\frac{a_i}{val}~. Do nếu ta có ~x~ thoả mãn ~\lfloor \frac{a_i}{x} \rfloor = val~, thì ~x \le \frac{a_i}{val}~, từ đó ta chọn được số lớn nhất mà vẫn thoả mãn điều kiện.
• Với ~k \in [u, v]~, ta có ~l = i - k + 1~. Như vậy ~a_i~ sẽ đóng góp vào các truy vấn có ~l \in [i-v+1, i-u+1]~ một lượng: ~(i-l+1) \times val = (i+1) \times val - l \times val~
• Như vậy ta cần xử lý các truy vấn: Trừ ~(i+1) \times val~ và cộng ~l \times val~ vào đáp án của các ~l~ trong đoạn. Đây là một bài toán cổ điển, có thể giải bằng Prefix Sum:
  • Duy trì 2 mảng ~D_1~ dùng để cập nhật lượng hằng số ~(i+1) \times val~, và ~D_2~ dùng để cập nhật hệ số của ~L~ tăng lên một lượng là ~val~.
  • Với mỗi yêu cầu tăng đoạn ~[L,R]~, ta tăng ~D_1[L]~ và giảm ~D_1[R+1]~ một lượng ~(i+1) \times val~, đồng thời tăng ~D_2[L]~ và giảm ~D_2[R+1]~ một lượng ~val~.
  • Cuối cùng, cộng dồn hai mảng ~D_1~ và ~D_2~, khi đó đáp án cho truy vấn ~[L,n]~ sẽ là ~D_1[L] - D_2[L] \times L~.

Độ phức tạp: ~\mathcal{O}(n\sqrt{A})~. Cài đặt mẫu:

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int a[N];
int n, q;
int64_t add_i[N];
int64_t suff[N];
int64_t add_c[N];
int64_t ans[N];

// a[i] += i * val_i + val_c
void add(int l, int r, int val_i, int64_t val_c) {
  add_i[l] += val_i;
  add_i[r + 1] -= val_i;
  add_c[l] += val_c;
  add_c[r + 1] -= val_c;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = n; i >= 1; i--) {
    suff[i] = suff[i + 1] + a[i];
  }
  for (int i = 1; i <= n; i++) {
    for (int l = 1; l <= a[i];) {
      int k = a[i] / l;
      int r = a[i] / k;
      int low = i - r + 1, high = i - l + 1;
      low = max(low, 1);
      high = min(high, n);
      if (low <= high) {
        add(low, high, k, 1ll * i * k);
      }
      l = r + 1;
    }
  }
  for (int i = 1; i <= n; i++) {
    add_i[i] += add_i[i - 1];
    add_c[i] += add_c[i - 1];
    ans[i] = add_c[i] - 1ll * (i - 1) * add_i[i];
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << suff[l] - ans[l] << '\n';
  }
  return 0;
}

Subtask 4: Không có giới hạn gì thêm

Ý tưởng của subtask này vẫn dựa trên việc tính đóng góp của từng phần tử ~a_i~ giống subtask 3, nhưng ~r~ thay đổi qua các truy vấn, nên ta sử dụng kỹ thuật sweepline: duyệt ~r~ từ ~1~ đến ~n~. Khi xét đến ~a_r~, ta cập nhật đóng góp của nó vào các vị trí ~l~, sau đó trả lời các truy vấn kết thúc tại ~r~.

Vì phải trả lời truy vấn online trong khi đang sweepline, ta không thể dùng mảng cộng dồn tĩnh. Thay vào đó, ta cần một cấu trúc dữ liệu hỗ trợ cập nhật điểm và truy vấn tổng tiền tố. Một trong những cấu trúc hỗ trợ là Fenwick Tree.

Cài đặt sử dụng Fenwick Tree, độ phức tạp ~\mathcal{O}(n \sqrt{A} \log n)~:

#include <bits/stdc++.h>

using namespace std;

template <class T>
struct FT {
  vector<T> ft;
  FT(int _n = 0) { ft.assign(_n + 5, 0); }
  void upd(int id, T val) {
    for (; id < (int)ft.size(); id += id & -id) ft[id] += val;
  }
  T get(int id) {
    T ans = 0;
    for (; id > 0; id -= id & -id) ans += ft[id];
    return ans;
  }
};

struct S {
  int64_t add_c, add_i;
  S(int64_t c = 0, int64_t i = 0) : add_c(c), add_i(i) {}
  S& operator+=(const S& rhs) {
    add_c += rhs.add_c;
    add_i += rhs.add_i;
    return *this;
  }
};

const int N = 2e5 + 5;

int a[N];
int n, q;
int64_t pref[N];
int64_t ans[N];
vector<pair<int, int>> que[N];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  for (int i = 1; i <= q; i++) {
    int l, r;
    cin >> l >> r;
    que[r].emplace_back(l, i);
  }
  FT<S> ft(n);
  for (int i = 1; i <= n; i++) {
    for (int l = 1; l <= a[i];) {
      int k = a[i] / l;
      int r = a[i] / k;
      int low = i - r + 1, high = i - l + 1;
      low = max(low, 1);
      high = min(high, n);
      if (low <= high) {
        ft.upd(low, S(1ll * i * k, k));
        ft.upd(high + 1, S(-1ll * i * k, -k));
      } else {
        break;
      }
      l = r + 1;
    }
    for (auto [l, idx] : que[i]) {
      auto [add_c, add_i] = ft.get(l);
      ans[idx] = pref[i] - pref[l - 1] - (add_c - 1ll * (l - 1) * add_i);
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}

Tuy nhiên, với giới hạn ~2 \cdot 10^5~ thì thuật toán trên không thể chạy được trong thời gian cho phép. Nhận thấy bài toán có đặc thù là số lượng truy vấn cập nhật rất nhiều (~n\sqrt{A}~), nhưng số truy vấn hỏi lại ít hơn (~q~), nên ta sẽ đổi sang sử dụng một cấu trúc dữ liệu khác, hỗ trợ cập nhật nhanh nhưng truy vấn chậm hơn một chút, đó là sử dụng chia căn:

• Chọn một hằng số ~B~, và chia mảng thành ~\frac{n}{B}~ đoạn.
• Lưu 2 mảng: ~\text{blk}_i~ thể hiện tổng của các phần tử trong khối thứ ~i~, và ~f_i~ thể hiện giá trị của phần tử thứ ~i~. Lưu ý ta cần duy trì 2 cấu trúc riêng biệt cho ~D_1~ và ~D_2~.
• Với mỗi truy vấn tăng một điểm ~i~, ta tăng ~\text{blk}_{\frac{i}{B}}~ và ~f_i~. Độ phức tạp ~\mathcal{O}(1)~.
• Với mỗi truy vấn tìm tổng của ~i~ phần tử đầu tiên, ta duyệt trâu từng block theo chỉ số ~b~ tăng dần:
  • Nếu block hiện tại nằm bên trái ~i~, ta cộng ~\text{blk}_b~ vào kết quả.
  • Nếu block hiện tại chứa ~i~, ta duyệt trâu từ đầu block (~b \times B~) đến ~i~, và cộng kết quả với ~f_i~. Sau đó dừng duyệt block.
  • Vậy việc truy vấn mất ~\mathcal{O}(B + \frac{n}{B})~.
• Để tối ưu ta chọn ~B \approx \sqrt{n}~. Độ phức tạp cho toàn bài toán chỉ còn ~\mathcal{O}(n \sqrt{A} + q \sqrt{n})~.

Cài đặt sử dụng chia căn:

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const int B = 700;
const int NB = N / B + 5;

struct S {
  int64_t add_c, add_i;
  S(int64_t c = 0, int64_t i = 0) : add_c(c), add_i(i) {}
  S& operator+=(const S& rhs) {
    add_c += rhs.add_c;
    add_i += rhs.add_i;
    return *this;
  }
};

struct Sqrt {
  S buc[NB];
  S a[N];
  Sqrt() {
    for (int i = 0; i < N; i++) a[i] = S();
    for (int i = 0; i < NB; i++) buc[i] = S();
  }
  void add(int pos, S val) {
    int blk = pos / B;
    a[pos] += val;
    buc[blk] += val;
  }
  S get(int pos) {
    S tot = S();
    int blk = pos / B;
    for (int i = 0; i < blk; i++) {
      tot += buc[i];
    }
    for (int i = blk * B; i <= pos; i++) {
      tot += a[i];
    }
    return tot;
  }
} ds;

int a[N];
int n, q;
int64_t pref[N];
int64_t ans[N];
vector<pair<int, int>> que[N];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL
#define task "a"
#else
#define task ""
#endif
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  for (int i = 1; i <= q; i++) {
    int l, r;
    cin >> l >> r;
    que[r].emplace_back(l, i);
  }
  for (int i = 1; i <= n; i++) {
    for (int l = 1; l <= a[i];) {
      int k = a[i] / l;
      int r = a[i] / k;
      int low = i - r + 1, high = i - l + 1;
      low = max(low, 1);
      high = min(high, n);
      if (low <= high) {
        ds.add(low, S(1ll * i * k, k));
        ds.add(high + 1, S(-1ll * i * k, -k));
      } else {
        break;
      }
      l = r + 1;
    }
    for (auto [l, idx] : que[i]) {
      auto [add_c, add_i] = ds.get(l);
      ans[idx] = pref[i] - pref[l - 1] - (add_c - 1ll * (l - 1) * add_i);
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}