VOJ - LEM4

Source: LEM4
Tags: Data Structures

Problem:
Cho một dãy N ô vuông thành một hàng, ban đầu ô vuông nào cũng màu trắng. Cho M truy vấn, mỗi truy vấn có dạng:
- 1 x y: Tô trắng các ô vuông từ x đến y.
- 2 x y: Tô đen các ô vuông từ x đến y.
- 3: In ra độ dài dãy có nhiều nhất các ô vuông trắng liên tiếp nhau.
1 ≤ N ≤ 1e4.
1 ≤ M ≤ 1e5.

Ví dụ:
Input:
6
7
2 1 2
2 4 5
3
1 3 4
3
1 1 1
3

Output:
1
2
2

Explanation:
Các ô vuông ban đầu:
☺☺☺☺☺☺
Sau các truy vấn:
2 1 2
☻☻☺☺☺☺
2 4 5
☻☻☺☻☻☺
3
→ 1
1 3 4
☻☻☺☺☻☺
3
→ 2
1 1 1
☺☻☺☺☻☺
3
→ 2

Solution:
Ta dựng một cây IT với mỗi nút chứa 3 giá trị chính như sau:
- left: Độ dài đoạn các ô trắng liên tiếp nằm ngoài cùng bên trái của đoạn mà nút đó quản lý.
- right: Độ dài đoạn các ô trắng liên tiếp nằm ngoài cùng bên phải của đoạn mà nút đó quản lý.

- ans: Độ dài đoạn các ô trắng liên tiếp dài nhất của đoạn mà nút đó quản lý.

Để việc update đoạn tránh bị TLE ta cần thực hiện Lazy Propagation. Dựng thêm một biến lazy lưu 3 giá trị 0, 1 và 2. Mỗi lần lazy down hoặc update, nếu lazy = 1 thì ans = left = right = độ dài đoạn, nếu lazy = 2 thì ans = left = right = 0, đối với thao tác lazy down nếu lazy của nút cha bằng 0 thì không cần update.

Mỗi lần update, gọi IT[k] là nút đang xét, IT[x] và IT[y] lần lượt là nút con trái và phải:

if IT[x].ans = độ dài đoạn nút con trái then

    IT[k].left = IT[x].ans + IT[y].left

else IT[k].left = IT[x].left

if IT[y].ans = độ dài đoạn nút con phải then

    IT[k].right = IT[x].right + IT[y].ans

else IT[k].right = IT[y].right

IT[k].ans = max(IT[x].right + IT[y].left, IT[x].ans, IT[y].ans)

Vì nếu IT[x].ans = độ dài đoạn nút con trái thì nguyên đoạn bên trái sẽ là màu trắng, do đó IT[k].left sẽ bằng độ dài đoạn bên trái cộng với IT[y].left, nếu không thì IT[k].left chính là IT[x].left, tương tự với IT[k].right. IT[k].ans chính là max đáp án riêng của 2 đoạn con với đoạn hợp giữa 2 đoạn con này (IT[x].right + IT[y].left).

Đáp án cho mỗi truy vấn 3 là IT[1].ans.

Độ phức tạp O(MlogN).

Code:

#include <iostream>

using namespace std;

struct data {

    int ans, left, right, lazy;

} IT[50015];

int n, m;

void lazy_down(int k, int l, int r) {

    if (IT[k].lazy == 0) return;

    IT[2 * k].lazy = IT[2 * k + 1].lazy = IT[k].lazy;

    IT[k].lazy = 0;

    k *= 2;

    IT[k].ans = IT[k].left = IT[k].right = (IT[k].lazy == 1 ? (l + r) / 2 - l + 1 : 0);

    ++k;

    IT[k].ans = IT[k].left = IT[k].right = (IT[k].lazy == 1 ? r - (l + r) / 2 : 0);

}

void update(int t, int x, int y, int k, int l, int r) {

    if (y < l || r < x) return;

    if (x <= l && r <= y)

        IT[k].ans = IT[k].left = IT[k].right = ((IT[k].lazy = t) == 1 ? r - l + 1 : 0);

    else {

        lazy_down(k, l, r);

        update(t, x, y, 2 * k, l, (l + r) / 2);

        update(t, x, y, 2 * k + 1, (l + r) / 2 + 1, r);

        if (IT[2 * k].ans == (l + r) / 2 - l + 1)

            IT[k].left = IT[2 * k].ans + IT[2 * k + 1].left;

        else IT[k].left = IT[2 * k].left;

        if (IT[2 * k + 1].ans == r - (l + r) / 2)

            IT[k].right = IT[2 * k].right + IT[2 * k + 1].ans;

        else IT[k].right = IT[2 * k + 1].right;

        IT[k].ans = max(IT[2 * k].right + IT[2 * k + 1].left, max(IT[2 * k].ans, IT[2 * k + 1].ans));

    }

}

int main() {

    cin >> n >> m;

    update(1, 1, n, 1, 1, n);

    for (int t, x, y; m--;) {

        cin >> t;

        if (t == 3)

            cout << IT[1].ans << '\n';

        else

            cin >> x >> y,

            update(t, x, y, 1, 1, n);

    }

}