---
author: Thienhx
tags: Ad-Hoc, Divide And Conquer
title: CNT
license: Public domain

image: https://i.imgur.com/iy1Vcd1.png
---

$\Huge \text{CNT - Trại Hè Miền Trung 2022}$

------

:::info
>🔗Links: [Đề bài](https://drive.google.com/file/d/1GrjlFCweQqB-Qg3_-Z7mJB0OkdnRorlx/view?usp=share_link)
>📌Tags: `Ad-Hoc` `Divide And Conquer`
>✍🏻Writer: [@Thienhx](https://hackmd.io/@Thienhx)
>📋Content:
>[TOC]
>
>[color=blue]
:::

------

## Giới Thiệu

Ta có một bảng $n$ x $m$ ô vuông, các hàng được đánh số từ $0$ đến $n - 1$, cột từ 0 đến $m - 1$
một ô

Một ô $\text{(i, j)}$ được gọi là cắt đi nếu như $\text{(i AND j) > 0}$


Ta có q truy vấn, mỗi truy vấn thuộc dạng $x$, $y$, $u$, $v$:

Ta cần tính số mảnh giấy nhận được khi cắt theo đường biên ngoài
của hình chữ nhật có góc trên trái là $\text{(x, y)}$ và góc dưới phải là $\text{(u, v)}$

## Subtask 1

$\Large n, m, q \leq 200$

Rõ ràng bài toán có thể được giải quyết bằng cách dfs / bfs những vùng nằm ở trong hình chữ nhật, sau đó kết quả sẽ là số lượng thành phần liên thông mà có AND của các phần tử $= 0$

ĐPT thuật toán: $O(n * m * q)$

## Subtask 2

$\Large n, m, q \leq 2000$

Bây Giờ thuật bfs sẽ là quá chậm, ta phải nhìn kĩ hơn về bản chất của bảng

Sau đây là bảng $16$ x $16$, cho ta thấy rõ hơn về bài toán:
Ô giá trị $0$ nghĩa là có $\text{AND = 0}$, còn $1$ là có $\text{AND > 0}$

> $\text{0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0}$
> $\text{0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1}$
> $\text{0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1}$
> $\text{0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1}$
> $\text{0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1}$
> $\text{0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1}$
> $\text{0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1}$
> $\text{0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1}$
> $\text{0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1}$
> $\text{0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1}$
> $\text{0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1}$
> $\text{0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1}$
> $\text{0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1}$
> $\text{0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1}$
> $\text{0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1}$
> $\text{0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1}$

Ta có thể thấy được rằng những ô có giá trị $0$ thì một
trong $2$ ô ở trên hoặc ở bên trái của nó cũng sẽ có giá trị $0$

### Một số ví dụ

Ta sẽ phân tích tính chất này rõ hơn và chứng minh nó:

> giả sử ta có $\text{(x AND y) = 0}$, lấy ví dụ là $\text{(x = 18, y = 40)}$
> Khi ta phân tích 2 số này thành hệ nhị phân ta sẽ được:
> $18 = 010010$
> $40 = 101000$

> Thì khi ta xét ô $\text{(17, 40)}$ ta sẽ được:
> $17 = 010001$
> $40 = 101000$
> $\text{(17 AND 40) = 0}$

> Xét ô $\text{(18, 39)}$ ta sẽ được:
> $18 = 010010$
> $39 = 100111$
> $\text{(18 AND 39) = 2}$

Ta thấy chỉ có một trong $2$ ô $\text{(17, 40)}$ hoặc $\text{(18, 39)}$ sẽ có giá trị 0

Thật vậy, giả sử ta có $2$ giá trị $a, b$ bất kì dưới hệ nhị phân
ta gọi vị trí bit $1$ đầu tiên của $a$ là $p1$, của $b$ là $p2$

khi một giá trị được $-1$ thì bit $1$ đầu tiên sẽ biến từ $100000 -> 011111$

Thế nên khi $\text{p1 > p2}$ thì $\text{(a, b - 1)}$ sẽ có $\text{AND = 0}$
còn ngược lại thì $\text{(a - 1, b)}$ sẽ có $\text{AND = 0}$

### Tính chất bài toán

$\text{=> với mỗi ô có giá trị AND = 0 ở trong hình chữ nhật, sẽ có một đường đi từ}$
$\text{nó tới một ô có giá trị 0 ở trên hàng x, hoặc là cột y}$

$\text{=> Hay nói cách khác, nó sẽ thuộc cùng thành phần liên}$
$\text{thông với một ô có giá trị = 0 ở hàng x hoặc cột y}$

Bây giờ bài toán đưa về đếm thành phần liên thông ở trên hàng $x$ và cột $y$

Bài toán có thể được giải quyết bằng thuật bfs / dfs
hoặc đơn giản là đếm số đoạn $0$ liên tiếp trên hàng $x$ và cột $y$

ĐPT thuật toán: $O(q * (n + m))$

## Subtask 3

$\Large n, m \leq 10^9 \Large \text{,}\ \Large q \leq 10^5$

### ý tưởng chính
bây giờ ta ko thể bfs để tìm thành phần liên thông được nữa, vì số lượng ô trong bảng quá lớn

Bây giờ ta có thể tạo ra hàm $\text{Calc(x, n)}$ trong đó $x$ là hàng hiện tại và $n$ là số cột, hàm sẽ trả về số thành phần liên thông trong n cột đầu tiên ở hàng $x$

>Giả sử ta xét $x = 2$ ở bảng trên:
>$0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1$
>
>Và biểu diễn nhị phân của $2$:
>$10$

>Rõ ràng ban đầu ta sẽ luôn có số $0$, vì $(x\ AND\ 0) = 0\
>(\forall x \geq 0)$

>khi xét tới bit thứ $i$ ta có $2$ trường hợp:
>bit $i = 0$:
> * ta có thể lặp lại hoàn toàn quá trình ta vừa trải qua
> * hay nói cách khác ta gấp đôi dãy hiện tại
>
>bit $i = 1$:
> * $2^i$ giá trị tiếp theo bit thứ $i$ sẽ bật, điều đó dẫn đến việc $AND$ của nó với $x$ sẽ $> 0$

khi ta có được hàm x ta chỉ việc lấy $\text{Calc(x, r + 1) - Calc(x, l)}$ để lấy số thành phần liên thông trên hàng x và trên các cột từ l đến r (đánh số từ 0)

### Thuật toán

$\large \text{Từ đó ta sẽ có thuật toán để xây dựng lại hàng x:}$

>Đi qua các bit của $x$:
>bit $i = 0$:
> * Ta sẽ gấp đôi dãy hiện tại đang có
>
>bit $i = 1$:
> * Ta sẽ lấp đầy dãy bằng $2^i$ số $1$

*Lưu ý là số thành phần liên thông chỉ có thể tăng khi đã đi qua ít nhất $1$ bit $1$

### Cài đặt

Trong quá trình xây dựng dãy ta chỉ cần dữ chỉ số $len$, $cnt$, và $valid$:
>$\text{len: độ dài dãy}$
>$\text{cnt: số thành phần liên thông}$
>$\text{valid: nếu ta đã gặp ít nhất 1 bit 1 hay chưa}$

Bởi vì ta chỉ quan tâm tới n cột đầu của hàng nên ta không thể sinh hết len phần tử đầu được, ta có thể chia để trị kết quả như sau:

ll calc(ll x, ll n) {
    if (n <= 1) return n;
 
    bool valid = false;
    ll tmp = x, len = 1, cnt = 1;
    while(x) {
        len *= 2;
        valid = (valid || (x & 1));
        if (!(x & 1) && valid) cnt *= 2;
 
        x >>= 1;
        if (len * 2 >= n)
            return (!(x & 1) && valid ? cnt + calc(tmp, n - len) : cnt);
    }
    
    return (valid ? (n / len) * cnt : 1) + calc(tmp, n % len);
}

Trong quá trình ta xây dựng dãy, nếu $\text{len * 2 >= n}$ thì ta sẽ trả về
cnt và cộng thêm $\text{Calc(x, n - len)}$ nếu bit tiếp theo là bit $0$
(nghĩa là dãy hiện tại của ta sẽ được gấp đôi lượt sau, nếu là bit 1 thì dãy nay này chỉ toàn là số $1$ nên ta không quan tâm)

còn nếu $\text{len <= n}$ thì ta nhận thấy mọi bit sau này sẽ toàn là $0$, nên sẽ tồn tại chu kỳ len lặp lại, lúc đó thì ta đơn giản trả về:

$\text{Valid = false: 1 +}$ $\text{Calc(x, n % len)}$
$\text{Valid = true: }$ $\left \lfloor \frac{n}{len} \right \rfloor * cnt\ +$ $\text{Calc(x, n % len)}$

ĐPT thuật toán: $O(q * log(n)^2)$
*Lưu ý là có thể tối ưu đến $O(q * log(n))$ nhưng sẽ cài đặt khó hơn

$\text{Bạn có thể tham khảo chi tiết hơn về code ở}$ [đây](https://ideone.com/88Rvup) -> $O(q * log(n)^2)$