Hướng dẫn cho Khảo sát các tổ chức (Contest Practice VNOI 2021 Round 5)

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: Flower_On_Stone

Subtask 1: \(k \le 2, q \le 100\)

Giả sử sau khi sử dụng \(t\) thông tin về \(t\) người đặc biệt đầu danh sách, số người không phải là người đặc biệt của mỗi tổ chức là \(a_1,a_2,a_3,...,a_k\) (lúc đầu \(a=n\)).
Để \(s\) nhỏ nhất thì \(s-t\) người còn lại phải tham gia nhiều tổ chức nhất có thể, mỗi người sẽ lần lượt tham gia vào \(d\) tổ chức hiện đang có nhiều người nhất. Ngoài ra, tổ chức \(i\) cần thêm chính xác \(a_i\) người không đặc biệt tham gia. Đặt \(sum=a_1+a_2+a_3+..+a_k, mx=max\{a_1,a_2,a_3,...,a_k\}\), ta có \(s-t=max\{\lceil sum / d \rceil,mx \}\).

Subtask 2: \(k \le 10^5, q \le 100\)

Với mỗi người đặc biệt ta cập nhật mảng a (giảm đoạn liên tục \([L..R]\) đi 1 đơn vị) và thực hiện tính toán trong \(O(n)\)

Subtask 3: \(k,q \le 10^5, L = R\)

Người đặc biệt chỉ tác động tới một phần tử của a. Cần một CTDL để tìm max trong \(O(log_2(k))\) với mỗi \(0 \le t \le q\).

Subtask 4:

Tổng sum có thể được cập nhật trong \(O(1)\). Để giảm đoạn liên tiếp trên mảng a, ta sử dụng kĩ thuật lazy update trên Segment Tree.

Độ phức tạp: \(O(qlog_2(k))\)

Source code:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5 + 5;

int a[maxn];

struct Segment_Tree_Lazy
{
    struct Data_of_Node
    {
        ll value, mvalue, lazy;

        Data_of_Node(ll _value = 0, ll _mvalue = 0, ll _lazy = 0) : value(_value), mvalue(_mvalue), lazy(_lazy){};
    };

    Data_of_Node Node[maxn * 4];

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            Node[id].value = a[l];
            Node[id].mvalue = a[l];
            return;
        }

        int mid = (l + r) / 2;

        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        Node[id].value = Node[id * 2].value + Node[id * 2 + 1].value;
        Node[id].mvalue = max(Node[id * 2].mvalue, Node[id * 2 + 1].mvalue);
    }

    void down(int id, int l, int r)
    {
        ll value = Node[id].lazy;
        int mid = (l + r) / 2;

        Node[id * 2].value += value * (mid - l + 1);
        Node[id * 2].mvalue += value;
        Node[id * 2].lazy += value;

        Node[id * 2 + 1].value += value * (r - mid);
        Node[id * 2 + 1].mvalue += value;
        Node[id * 2 + 1].lazy += value;

        Node[id].lazy = 0;
    }

    void upd(int id, int l, int r, int u, int v)
    {
        if (l > v || r < u)
            return;

        if (l >= u && r <= v)
        {
            Node[id].value -= 1ll * (r - l + 1);
            Node[id].mvalue -= 1;
            Node[id].lazy -= 1;
            return;
        }

        down(id, l, r);
        int mid = (l + r) / 2;

        upd(id * 2, l, mid, u, v);
        upd(id * 2 + 1, mid + 1, r, u, v);
        Node[id].value = Node[id * 2].value + Node[id * 2 + 1].value;
        Node[id].mvalue = max(Node[id * 2].mvalue, Node[id * 2 + 1].mvalue);
    }
};

Segment_Tree_Lazy St;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k, q;
    cin >> n >> k >> q;

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

    St.build(1, 1, n);

    cout << max(St.Node[1].mvalue, (St.Node[1].value + 1ll * k - 1) / k) << '\n';

    for (int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        St.upd(1, 1, n, l, r);
        cout << max(St.Node[1].mvalue, (St.Node[1].value + 1ll * k - 1) / k) + i << '\n';
    }
    return 0;
}

Bình luận

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

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