Solution [HNOI2021 - V1 - THPT] Bài 3: Phát đồng xu

Subtask 1

• Với ~n, m \le 10^3~, ta có thể dùng vòng lặp for để update cho mỗi thao tác. Sau ~m~ thao tác, ta thu được số đồng xu của mỗi người, từ đó tính được kết quả.
• Độ phức tạp ~O(n * m)~.

Subtask 2

• Với ~n, m \le 10^5~, dễ thấy thuật toán trâu đã không còn hiệu quả.

• Đầu tiên, giả sử như trong m thao tác các truy vấn đều có ~l \le r~ vậy ta cần giải quyết như thế nào?

  • Đây là một bài toán con khá phổ biến và hữu dụng. Cụ thể ta cần làm như sau với mỗi truy vấn: ~a_l++~, ~a_{r + 1}--~
  • Sau m truy vấn, lúc này, ta thực hiện thao tác: for (int i=1; i<=n; i++) a[i] += a[i-1]
  • Như vậy, lúc này, giá trị ~a_i~ chính là số đồng xu của người ~i~ sau ~m~ thao tác.
  • Tới đây ta có thể dễ dàng xử lý kết quả.

• Tuy nhiên, bài này lại đặc biệt hơn ở việc các thao tác sẽ update theo chiều kim đồng hồ. Dù vậy, chúng ta cũng chỉ cần xử lý thêm một chút với trường hợp ~l > r~:

  • Chúng ta sẽ tách nó thành 2 pha.
  • Pha đầu tiên, ta cần tăng đoạn ~[l,n]~ lên ~1~ đơn vị.
  • Pha tiếp theo, ta cần tăng đoạn ~[1,r]~ lên ~1~ đơn vị.
  • Cách tăng giống hệt như bài toán con đã nêu ở trên.

• Như vậy, ta có thể tính được số xu của mỗi người sau ~m~ thao tác, với độ phức tạp chỉ ~O(n + m)~. Đến đây việc tính ra kết quả của bài toán là khá đơn giản.

Subtask 3

• Ở subtask này, do ~n~ lên tới ~10^9~ nên ta không thể sử dụng mảng để lưu các giá trị của ~n~ người nữa.

• Lúc này, ở bước update các truy vấn, ta cần sử dụng cấu trúc dữ liệu map.

• Vấn đề bây giờ là bước tính kết quả, thay vì có mảng đề cộng dồn chúng lại, ta lại có một map các giá trị.

• Tuy vậy, ta vẫn chỉ cần làm y nguyên như cũ, ta có một biến ~sum~ để lưu tổng hiện tại, biến ~res~ lưu giá trị max hiện tại, biến ~freq~ lưu số lần giá trị ~res~ xuất hiện.

• Ta sẽ tiến hành thủ tục sau:

    int sum = 0;
    for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
        sum += it -> second;
        if(sum > res){
            res = sum;
            int tmp = it -> first;
            it++;
            freq = it -> first - tmp;
            it--;
        } else if (sum == res) {
            int tmp = it -> first;
            it++;
            freq += it -> first - tmp;
            it--;
        }
    }
    cout << res << " " << freq;

• Lí do là bởi, gọi ~a~ = key hiện tại, ~b~ = key tiếp theo (trong map), thì đoạn những người trong đoạn ~[a, b - 1]~ sẽ có số đồng xu bằng nhau.

• Độ phức tạp ~O((n + m) * log)~.

Code mẫu

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

#include <bits/stdc++.h>
#define int long long
#define task "BAI3"
using namespace std;

template<class X, class Y> 
bool minimize(X &a, Y b) 
{
    if (a > b)
    {
        return a = b, true;
    }
    return false;
}

template<class X, class Y> 
bool maximize(X &a, Y b) 
{
    if (a < b)
    {
        return a = b, true;
    }
    return false;
}

int test = 1;
int n, m;
int l, r;
map<int, int> mp;
int res = 0, freq = 0;

void ReadData() 
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> l >> r;
        if (l <= r) {
            mp[l]++;
            mp[r + 1]--;
        } else {
            mp[l]++;
            mp[1]++;
            mp[r + 1]--;
            mp[n + 1]--;
        }
    }
}

void Solve()
{
    int sum = 0;
    for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) {
        sum += it -> second;
        if (sum > res) {
            res = sum;
            int cur = it -> first;
            it++;
            freq = it -> first - cur;
            it--;
        } else if (sum == res) {
            int cur = it -> first;
            it++;
            freq += it -> first - cur;
            it--;
        }
    }
    cout << res << " " << freq;
}

signed main()
{
    if (fopen(task".inp", "r")) 
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //cin >> test;
    while(test--) 
    {
        ReadData();
        Solve();
        cout << "\n";
    }
}