Hướng dẫn cho LQDOJ CUP 2022 - Round 3 - SHOPPING

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: BJMinhNhut

Subtask $1$ ($20\%$ số điểm): Các giả thuyết có $k$ bằng nhau và $u=1$, $v=10^9$.

Tutorial

Do $u \leq a_i \leq v$, nên ta có thể phát biểu bài toán thành đếm số lượng vị trí $r$ sao cho $\sum_{i = l}^r a_i \leq k$.

Do $k$ bằng nhau với mọi truy vấn, ta tiến hành sắp xếp các truy vấn theo $l$, sau đó tìm $f(l)$ là vị trí $r$ phải nhất sao cho $sum[l, r] \leq k$. Ta có thể dễ dàng tìm bằng kĩ thuật hai con trỏ. Đáp án cho truy vấn sẽ là $f(l) - l + 1$.

Độ phức tạp: $\mathcal{O}(n + q\log q)$.

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_Q = 100005;

struct Query {
    int l, u, v, k, index;

    bool operator<(Query const &a) const {
        return l < a.l;
    }
};

int n, numQuery;
int a[MAX_N];
Query queries[MAX_Q];
int answer[MAX_Q];

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

    freopen("SHOPPING.inp", "r", stdin);
    freopen("SHOPPING.out", "w", stdout);

    cin >> n >> numQuery;

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

    for (int i = 1; i <= numQuery; i++) {
        cin >> queries[i].l >> queries[i].u >> queries[i].v >> queries[i].k;
        queries[i].index = i;
    }

    sort(queries + 1, queries + 1 + numQuery);
    int left = 0, right = -1;
    int sum = 0;
    for (int i = 1; i <= numQuery; i++) {
        while (left < queries[i].l) {
            sum -= a[left++];
        }

        while (right < n && sum <= queries[i].k - a[right + 1]) {
            sum += a[++right];
        }

        answer[queries[i].index] = right - left + 1;
    }

    for (int i = 1; i <= numQuery; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Subtask $2$ ($20\%$ số điểm): $a_i \leq 500$ với mọi $1 \leq i \leq n$.

Tutorial

Do $a_i \leq 500$, ta tiến hành tính $sum[v][r] = \sum_{i = 1, a_i \leq v}^r a_i$. Ta có thể tính trong $O(n \cdot a_i)$ theo công thức sau
$$sum[v][r] = \begin{cases} sum[v][r-1] + a_r & \text{nếu } a_r \leq v\\ sum[v][r-1] & \text{ngược lại} \end{cases}$$

Do khi $r$ càng lớn thì tổng cần tìm càng lớn, ta có thể trả lời truy vấn bằng cách chặt nhị phân để tìm $f(l)$. Với vị trí $r$, ta có thể tính tổng $g(l, r, u, v)$ trong $O(1)$ sau đó so sánh với $k$:

\[g(l, r, u, v) = (sum[v][r] - sum[v][l-1]) - (sum[u-1][r] - sum[u-1][l-1])\]

Độ phức tạp: $\mathcal{O}(n \cdot a + q)$.

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_Q = 100005;
const int MAX_A = 505;

struct Query {
    int l, u, v, k;
};

int n, numQuery;
int a[MAX_N];
Query queries[MAX_Q];
int prefix[MAX_A][MAX_N];
int ans[MAX_N];

int getSum(int maxV, int minV, int left, int right) {
    maxV = min(maxV, MAX_A - 1);
    minV = min(minV, MAX_A);
    return (prefix[maxV][right] - prefix[maxV][left - 1]) - (prefix[minV - 1][right] - prefix[minV - 1][left - 1]);
}

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

    freopen("SHOPPING.inp", "r", stdin);
    freopen("SHOPPING.out", "w", stdout);

    cin >> n >> numQuery;

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

    for (int i = 1; i <= numQuery; i++) {
        cin >> queries[i].l >> queries[i].u >> queries[i].v >> queries[i].k;
    }

    memset(prefix, 0, sizeof prefix);
    for (int i = 1; i <= n; i++) {
        for (int x = 0; x < MAX_A; x++) {
            prefix[x][i] = prefix[x][i - 1] + (x >= a[i] ? a[i] : 0);
        }
    }

    for (int i = 1; i <= numQuery; i++) {
        int left = queries[i].l, right = n;
        while (left <= right) {
            int mid = (right + left) >> 1;
            if (getSum(queries[i].v, queries[i].u, queries[i].l, mid) <= queries[i].k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        cout << right - queries[i].l + 1 << '\n';
    }

    return 0;
}

Subtask $3$ ($20\%$ số điểm): Các giả thiết có $v - u \le 5$.

Tutorial

Áp dụng ý tưởng chặt nhị phân và tính tổng theo giá trị của subtask 2, ta rời rạc hóa giá trị các phần tử của $a_i$ cùng với các giá trị $u, v$ trong các truy vấn. Dễ thấy có tối đa $n+2q$ giá trị phân biệt. Ta chia các phần tử vào các nhóm, mỗi nhóm gồm vị trí các phần tử có cùng giá trị. Từ đó ta có thể tính tổng $g(l, r, u, v)$ bằng cách đếm số phần tử trong đoạn $[l, r]$ của từng nhóm chứa các phần tử cùng giá trị $x \in [u, v]$.

Độ phức tạp: $\mathcal{O}((n + q) \log n)$.

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_Q = 100005;

struct Query {
    int l, u, v, k;
};

int n, numQuery;
int a[MAX_N];
Query queries[MAX_Q];
vector<int> vals;
vector<int> pos[MAX_N + 2 * MAX_Q];

int getPos(int val) {
    return lower_bound(vals.begin(), vals.end(), val) - vals.begin();
}

int getCnt(int val, int left, int right) {
    return upper_bound(pos[val].begin(), pos[val].end(), right) - lower_bound(pos[val].begin(), pos[val].end(), left);
}

long long getSum(int minV, int maxV, int left, int right) {
    long long result = 0;
    minV = getPos(minV);
    maxV = getPos(maxV);
    for (int val = minV; val <= maxV; val++) {
        result += 1ll * vals[val] * getCnt(val, left, right);
    }
    return result;
}

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

    freopen("SHOPPING.inp", "r", stdin);
    freopen("SHOPPING.out", "w", stdout);

    cin >> n >> numQuery;

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

    for (int i = 1; i <= numQuery; i++) {
        cin >> queries[i].l >> queries[i].u >> queries[i].v >> queries[i].k;
    }
    for (int i = 1; i <= n; i++) {
        vals.push_back(a[i]);
    }

    for (int i = 1; i <= numQuery; i++) {
        vals.push_back(queries[i].u);
        vals.push_back(queries[i].v);
    }

    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());

    for (int i = 1; i <= n; i++) {
        int x = getPos(a[i]);
        pos[x].push_back(i);
    }

    for (int i = 1; i <= numQuery; i++) {
        int left = queries[i].l, right = n;
        while (left <= right) {
            int mid = (right + left) >> 1;
            if (getSum(queries[i].u, queries[i].v, queries[i].l, mid) <= queries[i].k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        cout << right - queries[i].l + 1 << '\n';
    }

    return 0;
}

Subtask $4$ ($20\%$ số điểm): Các giả thiết có $u = 1$.

Tutorial

Áp dụng ý tưởng xử lí offline ở subtask 1 và chặt nhị phân ở subtask 2, trong subtask này, ta sắp xếp các truy vấn theo $v_i$ không giảm. Sau đó, ta duyệt truy vấn theo thứ tự đã sắp xếp, đồng thời duy trì một cây Fenwick tree lưu tổng các phần tử có giá trị không vượt quá $v_i$ theo vị trí các phần tử đó. Sau đó ta chặt nhị phân để tìm $f(l)$ bằng cách tính tổng $g(l, r, u, v)$ trên cây Fenwick tree để so sánh với $k$.

Để duy trì cây Fenwick tree, ta có thể sắp xếp các phần tử trong $a$ theo thứ tự không giảm, sau đó dùng kĩ thuật hai con trỏ để cập nhật lên cây các phần tử $a_x \leq v_i$.

Độ phức tạp: $\mathcal{O}(n\log n + q \log^2 n)$.

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_Q = 100005;

struct Query {
    int l, u, v, k, index;

    bool operator<(Query const &a) const {
        return u < a.u || (u == a.u && v < a.v);
    }
};

struct FenwickTree {
    int treeSize;
    vector<long long> nodes;

    void init(int treeSize) {
        this->treeSize = treeSize;
        nodes.assign(treeSize + 1, 0);
    }

    void update(int id, long long val) {
        for (; id <= treeSize; id += (id & -id)) {
            nodes[id] += val;
        }
    }

    long long get(int id) {
        long long result = 0;
        for (; id >= 1; id -= (id & -id)) {
            result += nodes[id];
        }
        return result;
    }

    long long get(int left, int right) {
        return get(right) - get(left - 1);
    }
};

int n, numQuery;
pair<int, int> a[MAX_N];
Query queries[MAX_Q];
FenwickTree fenwickTree;
int ans[MAX_Q];

int getBestPos(int initLeft, int value) {
    int left = initLeft, right = n;
    while (left <= right) {
        int mid = (right + left) >> 1;
        if (fenwickTree.get(initLeft, mid) <= value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}

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

    freopen("SHOPPING.inp", "r", stdin);
    freopen("SHOPPING.out", "w", stdout);

    cin >> n >> numQuery;

    for (int i = 1; i <= n; i++) {
        cin >> a[i].first;
        a[i].second = i;
    }

    for (int i = 1; i <= numQuery; i++) {
        cin >> queries[i].l >> queries[i].u >> queries[i].v >> queries[i].k;
        queries[i].index = i;
    }

    sort(queries + 1, queries + numQuery + 1);
    sort(a + 1, a + 1 + n);

    fenwickTree.init(n);
    int range = 0;
    for (int i = 1; i <= numQuery; i++) {
        while (range < n && a[range + 1].first <= queries[i].v) {
            ++range;
            fenwickTree.update(a[range].second, a[range].first);
        }

        int right = getBestPos(queries[i].l, queries[i].k);
        ans[queries[i].index] = right - queries[i].l + 1;
    }

    for (int i = 1; i <= numQuery; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Subtask $5$ ($20\%$ số điểm): Không có ràng buộc gì thêm.

Tutorial (Parallel Binary Search)

Xuất phát từ lời giải của subtask 4, ở subtask này ta cần thêm một cận $u$ cho giá trị của các phần tử khi tính tổng.

Nhận xét 1: Ở mỗi truy vấn, ta cần thông tin từ $2$ cây Fenwick tree: cây $F_1$ chứa các phần tử $\leq v$ (giống subtask 4), cây $F_2$ chứa các phần tử $< u$. Từ đó, trong mỗi lượt chặt nhị phân, ta có thể tính $g(l, r, u, v)$ bằng tổng đoạn $[l, r]$ trong cây $F_1$ trừ đi tổng đoạn $[l, r]$ trong cây $F_2$.

Nhận xét 2: Ở mỗi truy vấn, ta đều cần tìm cách dựng hai cây Fenwick tree, sau đó chặt nhị phân rồi dùng hai cây này để so sánh với $k$. Nếu dùng hai con trỏ để duy trì hai cây, độ phức tạp thuật toán có thể lên tới $O(n^2)$. Đồng thời, ta nhận thấy thao tác cập nhật các phần tử từ $1$ đến vị trí $x$ nào đó cho cây Fenwick sẽ được thực hiện lặp lại nhiều lần qua các truy vấn.

Lời giải: Từ hai nhận xét trên, ta cân nhắc kĩ thuật chặt nhị phân song song. Ở mỗi lượt chặt nhị phân, ta có danh sách các truy vấn cần giải quyết có dạng $(l, r, u, v)$: tính tổng các phần tử có giá trị thuộc $[u, v]$ nằm trong đoạn vị trí $[l, r]$. Ta tiến hành chia mỗi truy vấn này thành $2$ thao tác có dạng:

$(v, l, r, 1)$: Cộng tổng các phần tử nhỏ hơn hoặc bằng $v$ vào tổng cần tính của truy vấn.
$(u-1, l, r, -1)$: Trừ tổng các phần tử nhỏ hơn $u$ vào tổng cần tính của truy vấn.

Đồng thời, ta thêm thao tác $(i, a_i)$: cập nhật phần tử $a_i$ vào cây Fenwick tree.

Sau đó, ta sắp xếp các thao tác này theo giá trị của phần tử và tính tổng cho $q$ truy vấn với độ phức tạp chỉ là $O((q+n)\log n)$.

Độ phức tạp: $\mathcal{O}((n + q) \log^2 n)$.

Solution (Parallel Binary Search)

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_Q = 100005;

struct Query {
    int l, u, v, k;
};

struct BinarySearch {
    int left, right;

    BinarySearch(int _left = 0, int _right = 0) : left(_left), right(_right) {}

    int getMid() { return (right + left) >> 1; }

    bool finished() { return left > right; }

    void update(bool goLeft) {
        if (goLeft) {
            left = getMid() + 1;
        } else {
            right = getMid() - 1;
        }
    }
};

struct FenwickTree {
    int treeSize;
    vector<long long> nodes;

    void init(int treeSize) {
        this->treeSize = treeSize;
        nodes.assign(treeSize + 1, 0);
    }

    void update(int id, long long val) {
        for (; id <= treeSize; id += (id & -id)) {
            nodes[id] += val;
        }
    }

    long long get(int id) {
        long long result = 0;
        for (; id >= 1; id -= (id & -id)) {
            result += nodes[id];
        }
        return result;
    }

    long long get(int left, int right) {
        return get(right) - get(left - 1);
    }
};

struct Event {
    int maxVal, index, sign;

    Event(int _maxVal, int _index, int _sign) : maxVal(_maxVal), index(_index), sign(_sign) {}

    bool operator<(Event const &a) const {
        return maxVal < a.maxVal || (maxVal == a.maxVal && sign == 0);
    }
};

int n, numQuery;
int a[MAX_N];
long long tempSum[MAX_Q];
FenwickTree fenwickTree;
BinarySearch state[MAX_Q];
Query queries[MAX_Q];
vector<Event> events;

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

    freopen("SHOPPING.inp", "r", stdin);
    freopen("SHOPPING.out", "w", stdout);

    cin >> n >> numQuery;

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

    for (int i = 1; i <= numQuery; i++) {
        cin >> queries[i].l >> queries[i].u >> queries[i].v >> queries[i].k;
    }

    for (int i = 1; i <= n; i++) {
        events.push_back(Event(a[i], i, 0));
    }

    for (int i = 1; i <= numQuery; i++) {
        state[i] = BinarySearch(queries[i].l, n);
        events.push_back(Event(queries[i].u - 1, i, -1));
        events.push_back(Event(queries[i].v, i, 1));
    }

    sort(events.begin(), events.end());

    bool changed = true;
    while (changed) {
        changed = false;
        memset(tempSum, 0, sizeof(tempSum));
        fenwickTree.init(n);

        for (Event &cur : events) {
            if (cur.sign == 0) {
                fenwickTree.update(cur.index, cur.maxVal);
            } else if (!state[cur.index].finished()) {
                tempSum[cur.index] += fenwickTree.get(queries[cur.index].l, state[cur.index].getMid()) * cur.sign;
            }
        }

        for (int i = 1; i <= numQuery; i++) {
            if (!state[i].finished()) {
                changed = true;
                state[i].update(tempSum[i] <= queries[i].k);
            }
        }
    }

    for (int i = 1; i <= numQuery; i++) {
        cout << state[i].right - queries[i].l + 1 << '\n';
    }

    return 0;
}

Tutorial (Mo's Algorithm)

Dựa trên ý tưởng của subtask 1. Nếu chúng ta kiểm soát được các phần tử $a_i$ trong đoạn $[u, v]$ thì hoàn toàn có thể tính được kết quả của từng truy vấn bằng nhiều phương pháp khác nhau như chặt nhị phân, Segment tree $\ldots$

Khi $u$ và $v$ thay đổi thì hiển nhiên các phần tử chúng ta kiểm soát cũng thay đổi, và để thuận tiện trong việc kiểm soát các phần tử liên tục, chúng ta có thể sử dụng MO’s algorithm.

Trước tiên, dựa vào ý tưởng của subtask 3, chúng ta sẽ rời rạc hóa tất cả các giá trị $u, v$ và từng phần tử $a_i$. Lúc này với từng truy vấn chúng ta có thể dễ dàng kiểm soát các giá trị $a_i$ trong khoảng. Tuy nhiên sẽ có trường hợp nhiều phần tử $a_i$ cùng nằm tại $1$ điểm và khi chạy các truy vấn sẽ đi qua điểm đấy nhiều lần dẫn đến việc gia tăng độ phức tạp. Giải pháp cho vấn đề này là chúng ta sẽ tách các phần tử đấy ra thành các giá trị khác nhau sao cho vẫn thỏa mãn điều kiện nằm trong đoạn $[u, v]$. Sau khi hoàn thành bước này, độ phức tạp vẫn được đảm bảo là $O(\sqrt{n})$.

Bước tiếp theo, khi đã kiểm soát được các phần tử trong đoạn $[u, v]$, chúng ta sẽ tìm cách để trả lời cho từng truy vấn. Với việc thêm và xóa các phần tử liên tục, không khó để áp dụng cấu trúc Segment tree. Tuy nhiên khi dùng cấu trúc dữ liệu này thì độ phức tạp sẽ lên tới $O(n \sqrt{n} \log{n})$ (độ phức tạp quá lớn).

Một giải pháp khác chính là sử dụng mảng lưu tổng cho từng block. Khi chúng ta đã có được tổng cho từng block thì chỉ cần chạy qua từng block cho đến khi nào mà tổng hiện tại $> k$ thì chúng ta sẽ đi hẳn vào các phần tử trong block đấy rồi lại tiếp tục chạy đến khi nào tổng hiện tại $> k$ thì sẽ trả lời được truy vấn hiện tại. Độ phức tạp của giải pháp này là số block + số phần tử trong 1 block. Để thuận tiện chúng ta sẽ cố định số phần tử trong block là $\sqrt{n}$.

Độ phức tạp: $\mathcal{O}((n + 2q) \times \sqrt{n + 2q})$.

Solution (Mo's Algorithm)

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MAX_Q = 100005;
const int BLOCK = 855;

struct Query {
    int l, u, v, k, id;
    friend bool operator<(Query &A, Query &B) {
        if (A.u / BLOCK != B.u / BLOCK) {
            return A.u / BLOCK < B.u / BLOCK;
        }
        return A.v < B.v;
    }
};

int n, numQuery;
int a[MAX_N];
Query queries[MAX_Q];
vector<pair<int, int> > compress;
int valueAt[MAX_N + 2 * MAX_Q];
long long sum[MAX_N], sum_in_bl[MAX_N / BLOCK + 2];
int answer[MAX_Q];

void add(int pos, int val) {
    if (valueAt[pos] == 0) {
        return;
    }
    int x = valueAt[pos];
    sum[x] += val * a[x];
    sum_in_bl[x / BLOCK] += val * a[x];
}

int get(int pos, int k) {
    for (int i = pos; i <= min(n, (pos / BLOCK + 1) * BLOCK - 1); i++) {
        if (sum[i] > k) {
            return i - pos;
        } else {
            k -= sum[i];
        }
    }

    for (int i = pos / BLOCK + 1; i <= n / BLOCK; i++) {
        if (sum_in_bl[i] > k) {
            for (int j = max(0, i * BLOCK); j <= min(n, (i + 1) * BLOCK - 1); j++) {
                if (sum[j] > k) {
                    return j - pos;
                } else {
                    k -= sum[j];
                }
            }
            break;
        } else {
            k -= sum_in_bl[i];
        }
    }

    return n - pos + 1;
}

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

    freopen("SHOPPING.inp", "r", stdin);
    freopen("SHOPPING.out", "w", stdout);

    cin >> n >> numQuery;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        compress.emplace_back(a[i], -i);
    }

    for (int i = 1; i <= numQuery; i++) {
        cin >> queries[i].l >> queries[i].u >> queries[i].v >> queries[i].k;
        queries[i].id = i;
        compress.emplace_back(queries[i].u, i);
        compress.emplace_back(queries[i].v, i + numQuery);
    }

    sort(compress.begin(), compress.end(), [&](pair<int, int> &x, pair<int, int> &y) {
        if (x.first != y.first) {
            return x.first < y.first;
        }

        if (x.second < 0) {
            return (y.second > numQuery);
        }

        if (x.second <= numQuery) {
            if (y.second < 0) {
                return true;
            }
            return x.second < y.second;
        }

        return false;
    });

    for (int i = 0; i < (int)compress.size(); i++) {
        pair<int, int> x = compress[i];
        if (x.second < 0) {
            valueAt[i + 1] = -x.second;
        } else {
            if (x.second > numQuery) {
                queries[x.second - numQuery].v = i + 1;
            } else {
                queries[x.second].u = i + 1;
            }
        }
    }

    sort(queries + 1, queries + numQuery + 1);

    int curLeft = queries[1].u, curRight = queries[1].u - 1;

    for (int i = 1; i <= numQuery; i++) {
        while (curRight < queries[i].v) {
            add(++curRight, +1);
        }
        while (curRight > queries[i].v) {
            add(curRight--, -1);
        }
        while (curLeft < queries[i].u) {
            add(curLeft++, -1);
        }
        while (curLeft > queries[i].u) {
            add(--curLeft, +1);
        }
        answer[queries[i].id] = get(queries[i].l, queries[i].k);
    }

    for (int i = 1; i <= numQuery; i++) {
        cout << answer[i] << '\n';
    }

    return 0;
}

Cảm ơn bạn Trần Hoàng Sơn đã đóng góp lời giải Mo's Algorithm cho bài này.

Bình luận

Tải bình luận...

Không có bình luận nào.

Hướng dẫn cho LQDOJ CUP 2022 - Round 3 - SHOPPING

Subtask \(1\) (\(20\%\) số điểm): Các giả thuyết có \(k\) bằng nhau và \(u=1\), \(v=10^9\).

Subtask \(2\) (\(20\%\) số điểm): \(a_i \leq 500\) với mọi \(1 \leq i \leq n\).

Subtask \(3\) (\(20\%\) số điểm): Các giả thiết có \(v - u \le 5\).

Subtask \(4\) (\(20\%\) số điểm): Các giả thiết có \(u = 1\).

Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Bình luận