Codeforces - Rock-Paper-Scissors Champion

Source: Codeforces Round #528 (Div. 2): F. Rock-Paper-Scissors Champion
Tags: Data Structures

Problem:
N người chơi sẽ tham gia một giải đấu Oẳn tù tì, ban đầu họ đứng thành một hàng ngang theo thứ tự, và gửi trước cho ban tổ chức hình sẽ ra tại lượt đấu của mình (R: búa; P: bao; S: kéo), hình đã chọn sẽ được sử dụng cho tất cả ván đấu của người chơi đó sau này.
Giải đấu sẽ được diễn ra như sau, ban tổ chức chọn một cặp đấu kề nhau bất kỳ, người nào thua sẽ rời khỏi hàng, nếu cặp đấu hòa thì ban tổ chức sẽ tung đồng xu quyết định ai thua, các vị trí sát lại gần nhau sau khi người thua ra khỏi hàng, nhà vô địch của giải đấu là người còn lại cuối cùng.
Ban tổ chức đã nhận được danh sách sự lựa chọn của N người chơi, hãy giúp ban tổ chức xác định có bao nhiêu người chơi có khả năng trở thành nhà vô địch. Tuy nhiên giải đấu vẫn chưa diễn ra, vì vậy những người chơi có quyền thay đổi quyết định của mình và thông báo với ban tổ chức, với mỗi lần người chơi thay đổi quyết định, hãy đếm số lượng người chơi có khả năng trở thành nhà vô địch.
Dòng đầu là 2 số N, Q. Q là số lượt thay đổi quyết định của các người chơi.
Dòng thứ hai chứa N ký tự (R, P hoặc S) là lựa chọn ban đầu của các người chơi.
In ra Q + 1 dòng là số lượng người chơi có thể là nhà vô địch ban đầu và sau Q lượt thay đổi lựa chọn.
Q dòng tiếp theo mỗi dòng gồm số i và ký tự c nghĩa là người chơi thứ i sẽ thay đổi lựa chọn là sử dụng hình c.
1 ≤ N ≤ 2e5. 0 ≤ Q ≤ 2e5.

Ví dụ:
Input:
3 5
RPS
1 S
2 R
3 P
1 P
2 P

Output:

2

2

1

2

2

3

Explanation:

Ban đầu, lựa chọn của các người chơi là RPS.

Ban tổ chức có thể xếp trận 1-2 trước rồi 2-3, nhà vô địch là người chơi 3.

Ban tổ chức có thể xếp trận 2-3 trước rồi 1-3, nhà vô địch là người chơi 1.

Sau Q lượt thay đổi quyết định, lựa chọn của các người chơi là PPP.

Do tất cả các cách xếp lượt đấu đều hòa nên cả 3 người chơi đều có cơ hội trở thành nhà vô địch.

Solution: (đề đã vietsub thuần Việt do đó đừng hỏi sao mình dịch R là búa còn P là bao nghen :<)

Nếu bạn nhận xét được một người chơi có thể thắng hay không thì bạn hoàn toàn đã có thể giải được bài này. Vì các lựa chọn R, P, S đều thắng 1 hình khác và thua 1 hình khác như nhau, do đó ta lấy R làm đại diện để nhận xét, các hình khác đều tương tự.

Người chơi i lựa chọn hình R, ta bỏ qua những người chơi có cùng hình vì nếu đấu với họ thì chúng ta cũng sẽ có cơ hội thắng vì ban tổ chức sẽ tung đồng xu:

- Nếu trong giải đấu không có ai chọn P, chắc chắn người chơi i có cơ hội vô địch vì tất cả người chơi còn lại đều hòa hoặc thua người chơi i.

- Nếu trong giải đấu không có ai chọn S nhưng lại có người chọn P, người chơi i không thể có cơ hội vô địch vì người chơi chọn P không thể bị đánh bại.

- Nếu trong giải đấu đều có người chọn P và S, ta có các trường hợp như sau:

1) S .. R .. S

Trường hợp tồn tại hai người chơi chọn S bên trái và phải của người chơi i. Những người chơi chọn P sẽ bị triệt tiêu bởi những người chơi chọn S kề họ hoặc họ triệt tiêu lẫn nhau hoặc những người chơi chọn R khác, để rồi lại bị triệt tiêu bởi những người chơi chọn S khi kề họ, lúc này trong giải đấu chỉ còn lại những người chơi chọn S và R, do đó người chơi i hoàn toàn có khả năng đánh bại tất cả. Tất nhiên là trong các lượt đấu không xảy ra cặp đấu mà người chơi i thua. Vì ta có người chơi chọn S ở cả 2 bên do đó không tồn tại trường hợp một bên của người chơi i có chọn P nhưng không thể bị triệt tiêu (vì luôn có người chơi S triệt tiêu họ).

2) R .. S / S .. R

Trường hợp một bên người chơi i không tồn tại người chơi chọn hình nào khác, có thể coi người chơi i là ngoài cùng. Trường hợp này thật ra giống trường hợp trên, tuy nhiên không có người chơi chọn S ở bên còn lại nhưng cũng không có người chơi chọn P ở bên đấy, do đó trong trường hợp này người chơi i vẫn có thể vô địch.

Từ những nhận xét trên ta có thể đếm nhanh số lượng người chơi chọn R có thể vô địch là:

Gọi cnt(x, y) là số lượng người chơi chọn R trong đoạn [x, y], Sx là vị trí của người chơi trái nhất chọn S, Sy là vị trí của người chơi phải nhất chọn S, Px là vị trí của người chơi trái nhất chọn P, Py là vị trí của người chơi phải nhất chọn P:

- Trường hợp 1: cnt(Sx, Sy)

- Trường hợp 2: cnt(1, min(Sx, Px)) + cnt(max(Px, Py), N)

Tổng 2 trường hợp đối với mỗi sự lựa chọn R, P và S là đáp án.

Để tính cnt(x, y) nhanh ta sử dụng mảng prefix sum, nhưng để update thì ta cần đưa prefix sum này lên cây BIT. Để tìm các vị trí Sx, Sy, Px, Py ta có thể dùng set của C++ hoặc heap.

Độ phức tạp: O((N + Q)logN)

Code:

#include <iostream>

#include <set>

using namespace std;

int n, q, BIT[3][200015]; string s;

set <int> pos[3];

int mask(char c) {

    if (c == 'R') return 0;

    if (c == 'P') return 1;

    if (c == 'S') return 2;

}

void update(int m, int x, int k) {

    for (; x <= n; x += x & -x)

        BIT[m][x] += k;

}

int cnt(int m, int x, int y) {

    int res = 0;

    for (--x; x; x -= x & -x)

        res -= BIT[m][x];

    for (; y; y -= y & -y)

        res += BIT[m][y];

    return res;

}

#define first_pos(x) (*pos[x % 3].begin())

#define last_pos(x) (*(--pos[x % 3].end()))

int ans() {

    int res = 0;

    for (int i = 0; i < 3; ++i)

        if (!pos[(i + 1) % 3].size())

            res += pos[i].size();

        else if (pos[(i + 2) % 3].size())

            res += cnt(i, first_pos((i + 2)), last_pos((i + 2))),

            res += cnt(i, 1, min(first_pos((i + 1)), first_pos((i + 2)))),

            res += cnt(i, max(last_pos((i + 1)), last_pos((i + 2))), n);

    return res;

}

int main() {

    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> q >> s; s = ' ' + s;

    for (int i = 1; i <= n; ++i)

        update(mask(s[i]), i, 1),

        pos[mask(s[i])].insert(i);

    cout << ans() << '\n';

    while (q--) {

        int i; char c; cin >> i >> c;

        update(mask(s[i]), i, -1);

        pos[mask(s[i])].erase(i);

        update(mask(s[i] = c), i, 1);

        pos[mask(s[i])].insert(i);

        cout << ans() << '\n';

    }

}