$\text{🌱 Problem\_name}$

---

🔗 Link: https://lqdoj.edu.vn/problem/pvhoi20b1qol

📌 Tags: Binary Search, Prefix Sum

👤 Writer: @SPyofgame

👥 Contributor: @FireGhost , @matchamachiato

📋 Content:

• Hướng dẫn subtask 1
  • Code
• Hướng dẫn subtask 2
  • Code
• Hướng dẫn subtask 3
  • Code
• Hướng dẫn subtask 4
  • Code
• Hướng dẫn subtask 5
  • Code
• Hướng dẫn subtask 6
  • Code
• Hướng dẫn subtask 7
  • Code
• Tổng hợp
  • Bonus

---

Hướng dẫn subtask 1

Khi

$h=w=1$ thì ta cần tìm bảng con

$1\times 1$ có giá trị trung vị lớn nhất.

Có trung vị của dãy gồm một phần tử là chính nó.

Mà các giá trị trong bảng đều là hoán vị của dãy

$1\dots r\times c$ nên kết quả bài toán là

$r\times c$.

---

Code

Time:

$O(1)$
Space:

$O(1)$
Algo: Implementation

Code

int subtask1() 
{ 
    return r * c; 
}

---

Hướng dẫn subtask 2

Khi

$h=r$ và

$w=c$ thì ta cần tìm trung vị của cả bảng.

Mà các giá trị trong bảng đều là hoán vị của dãy

$1\dots r\times c$ nên kết quả bài toán là

$\frac{r\times c+1}{2}$.

---

Code

Time:

$O(1)$
Space:

$O(1)$
Algo: Implementation

Code

int subtask2()
{ 
    return (r * c + 1) / 2;
}

---

Hướng dẫn subtask 3

Duyệt qua các bảng

$w\times h$.

Với mỗi bảng mình lấy các giá trị đưa về mảng có độ dài

$w\times h$.

Sau khi sắp xếp mảng, mình có được giá trị trung vị là phần tử thứ

$\frac{(w\times h+1)}{2}$.

Trong các giá trị trung vị này mình lấy cái có giá trị lớn nhất.

---

Code

Time:

$O((r-w+1)(c-h+1)\times hw\times \log (hw))=O(r^2\times c^2\times \log (rc))$
Space:

$O(r\times c)$
Algo: Brute-forces, Sorting

Code

int value[LIM * LIM];
int subtask3()
{
    int res = 0;
    for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
    {
        for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
        {
            int p = 0;
            for (int x = lx; x <= rx; ++x)
                for (int y = ly; y <= ry; ++y)
                    value[++p] = a[x][y];

            sort(value + 1, value + p + 1);
            maximize(res, value[(p + 1) / 2]);
        }
    }

    return res;
}

---

Hướng dẫn subtask 4

Nhận xét: Thay vì sắp xếp như vậy, mình có thể dùng mảng đánh dấu để giảm bớt phần

$O(\log )$ đi.

Tuy độ phức tạp chỉ còn

$O(r^2\times c^2)$ có vẻ sẽ TLE với

$r=c=100$ nếu ta không cài cẩn thận.

Ta có thể tối ưu thêm bằng nhiều cách khác bằng nhánh cận:

• Không xét giá trị lớn hơn
  $max$ hay giá trị bé hơn
  $min$.
• Khi nào xét đủ
  $\frac{h\times w+1}{2}$ thì dừng.
• Hạn chế reset toàn bộ mảng nhiều lần.

Lúc này dù thuật là

$O(r^2\times c^2)$ nhưng sẽ không TLE vì hằng số giảm đi.

---

Code

Time:

$O(r\times c\times h\times w)$
Space:

$O(r\times c)$
Algo: Brute-forces, Frequency Array

Code

int used[LIM * LIM];
int subtask4()
{
    int timer = 0;
    memset(used, 0, sizeof(used));

    int res = 0;
    for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
    {
        for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
        {
            int mn = r * c;
            int mx = 1;
            ++timer;
            for (int x = lx; x <= rx; ++x)
            {
                for (int y = ly; y <= ry; ++y)
                {
                    minimize(mn, a[x][y]);
                    maximize(mx, a[x][y]);
                    used[a[x][y]] = timer;
                }
            }

            int cnt = (h * w + 1) / 2;
            for (int v = mn; v <= mx; ++v)
            {
                if (used[v] == timer)
                {
                    if (--cnt == 0)
                    {
                        maximize(res, v);
                        break;
                    }
                }
            }
        }
    }

    return res;
}

---

Hướng dẫn subtask 5

Nhận xét: Nếu ta di chuyển bảng sang phải, thì mỗi lần chỉ cập nhật thêm một cột mới và xóa 1 cột cũ.

Vậy với mỗi hàng có độ dài

$h$, mình tạo một tập các giá trị có trong

$w$ cột đầu tiên.

Sau đó mình sẽ thử lần lượt di chuyển qua phải, mỗi lần thêm

$1$ cột sang phải và xóa cột bên trái cùng, tới khi không đi được nữa.

Để thuận tiện cho việc tính toán, ta sử dụng cấu trúc dữ liệu dạng cây:

• Mỗi khi bắt đầu mình khởi tạo lại cấu trúc cây thành rỗng.
• Khi mình duyệt qua các cột mới, mình thêm phần tử vào cây.
• Khi duyệt lại các cột cũ, mình xóa phần tử đó ra khỏi cây.
• Để tính kết quả, mình lấy phần tử thứ
  $\frac{h\times w+1}{2}$ từ cây.

Sử dụng cây như thế nào cho đơn giản, ta có thể dùng Fenwick Tree:

• Coi mỗi phần tử đáng có trong tập là
  $+1$, và không có là
  $0$.
• Nếu xét trên một đoạn
  $[1,x]$ ra tổng - tức số phần tử, mà nhỏ hơn
  $\frac{h\times w+1}{2}$ thì trung vị nằm bên phải.
• Vì tổng chắc chắn sẽ không giảm khi kéo dài
  $[1,x]$ sang bên phải, nên ta có thể chặt nhị phân.
• Mục tiêu ta tìm là số có giá trị lớn nhất trong tập sao cho có đúng
  $\frac{h\times w+1}{2}$ só bé hơn hoặc bằng nó.

Về độ phức tạp:

• Mình duyệt qua
  $(r-h+1)$ đoạn hàng độ dài
  $h$.
• Mỗi hàng mình thêm và xóa tối đa
  $O(w)$ cột.
• Mỗi lần thêm/xóa/tìm một phần tử chỉ mất
  $O(\log (hw))$.
• Vậy độ phức tạp là
  $O((r-h+1)\times h\times w\times \log (rc))$.

Để tối ưu hằng số:

• Bạn có thể sử dụng cấu trúc dữ liệu Fenwick Tree, Binary Trie.
• Với mỗi đoạn hàng chỉ xét các giá trị trong đoạn min tới max.
• Hạn chế reset cấu trúc dữ liệu nhiều lần.
• Hạn chế thêm xóa những phần không còn xét nữa.

Để tối ưu độ phức tạp:

• Bạn có thể thử di chuyển cả trái phải trên dưới, lúc này chỉ còn
  $O((r-h+1)\times (c-w+1)\times min(h,w)\times \log (rc))$.
• Với mỗi bảng không xét lớn hơn max hay bé hơn min, lúc này chỉ còn
  $O((r-h+1)\times (c-w+1)\times min(h,w)\times \log (hw))$.
• Ngoài ra vì dãy là hoán vị nên có tồn tại cấu trúc dữ liệu để giảm xuống còn
  $O(\log \sqrt{hw})$ hoặc thậm chí bỏ mất
  $O(\log (hw))$.
• Bạn cũng có thể giảm bớt
  $O(min(h,w))$ bằng một số thuật toán đặc biệt dù bài này thì không cần .

---

Code

Time:

$O((r-h+1)\times h\times w\times \log (rc))$
Space:

$O(r\times c)$
Algo: Brute-forces, Data Structure, Sliding Window

Code

int bit[LIM * LIM];
void bit_construct()
{
    memset(bit, 0, sizeof(bit[0]) * (r * c + 1));
}

void bit_update(int p, int v)
{
    for (; p <= r * c; p += p & -p)
        bit[p] += v;
}

int bit_query(int p)
{
    int res = 0;
    for (; p >= 1; p -= p & -p)
        res += bit[p];

    return res;
}

int bit_median()
{
    int expected = (h * w + 1) / 2;
    int upper = r * c - expected + 1;
    int lower = expected;

    int res = -1;
    for (int l = lower, r = upper; l <= r; )
    {
        int m = (l + r) >> 1;
        if (bit_query(m) >= expected)
        {
            res = m;
            r = m - 1;
        }
        else 
        {
            l = m + 1;
        }
    }

    return res;
}

int subtask5()
{
    int res = 0;
    for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
    {
        bit_construct();
        for (int x = lx; x <= rx; ++x)
            for (int y = 1; y <= w; ++y)
                bit_update(a[x][y], +1);   

        for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
        {
            maximize(res, bit_median());

            if (ry == c) break;
            for (int x = lx; x <= rx; ++x)
            {
                bit_update(a[x][ly + 0], -1);
                bit_update(a[x][ry + 1], +1);
            }
        }
    }

    return res;
}

---

Hướng dẫn subtask 6

Tư tưởng fenwick tree trên kia là duyệt rồi tìm kiếm bằng chặt nhị phân.

Nhưng vì

$2$ hàm là độc lập nếu xét tập các giá trị không đổi, ta có thể lật ngược ra, chặt nhị phân kết quả và kiểm tra bằng duyệt.

Với giá trị

$v$ được chặt,

$v$ nằm trong

$[1\dots r\times c]$:

• Gọi
  $cnt(v)$ là số phần tử lớn hơn hoặc bằng
  $v$ tại một bảng
  $h\times w$ bất kì.
• Gọi
  $target=\frac{h\times w+1}{2}$ là phần tử mình cần tìm kiếm.
• Nếu tồn tại bẳng
  $h\times w$ có
  $cnt(v)\ge target$ thì kết quả chắc chắn không nhỏ hơn
  $v$.
• Trong các
  $v$ thỏa mãn mình chọn
  $v$ có giá trị lớn nhất.

Đê tính

$cnt(v)$ ta cũng làm tương tự như cách trên, tuy nhiên sẽ cho ra cùng độ phức tạp vì vẫn phải duyệt nhiều hàng mỗi lần thêm

$a_{i,j}$

Để tối ưu mình có thể dựng mảng

$b_{i,j}=\{\begin{array}{ll}1& a_{i,j}\ge v\\ 0& a_{i,j}<v\end{array}$

Lúc này bằng Fenwick Tree 2D thay cho Fenwick Tree 1D:

• Ta có thể thêm phần tử
  $b_{i_j}$ của trong
  $O(\log (r\times c))$.
• Ta có thể tính
  $cnt(v)=$ tổng các
  $b_{i,j}$ trong
  $O(log(r\times c))$.
• Lưu ý rằng ta không có thao tác xóa, mà chỉ có tối đa
  $O(r\times c)$ thao tác thêm.
• Vậy độ phức tạp là
  $O(r\times c\times \log (r\times c))$.

Dù không phải là tối ưu lắm, mình có thể giảm bớt kết quả cần kiểm tra thành đoạn

$[\frac{h\times w+1}{2}\dots r\times c-\frac{h\times w+1}{2}+1]$.

---

Code

Time:

$O(r\times c\times \log (r\times c{)}^2)$
Space:

$O(r\times c)$
Algo: 2D Data Structure, Binary Search

Code

int bit2d[LIM][LIM];
void bit2d_construct()
{
    for (int x = 1; x <= r; ++x)
        memset(bit2d[x], 0, sizeof(bit2d[x][0]) * (c + 1));
}

void bit2d_update(int x, int y, int v)
{
    for (int p = x; p <= r; p += p & -p)
        for (int q = y; q <= c; q += q & -q)
            bit2d[p][q] += v;
}

int bit2d_query(int x, int y)
{
    int res = 0;
    for (int p = x; p >= 1; p -= p & -p)
        for (int q = y; q >= 1; q -= q & -q)
            res += bit2d[p][q];

    return res;
}

void bit2d_area_update(int x, int y, int u, int v, int k)
{
    bit2d_update(u, v, +k);
    bit2d_update(u, y - 1, -k);
    bit2d_update(x - 1, v, -k);
    bit2d_update(x - 1, y - 1, +k);
}

int bit2d_area_query(int x, int y, int u, int v)
{
    int res = 0;
    res += bit2d_query(u, v);
    res -= bit2d_query(u, y - 1);
    res -= bit2d_query(x - 1, v);
    res += bit2d_query(x - 1, y - 1);
    return res;
}

int testing(int value, int target)
{
    bit2d_construct();
    for (int i = 1; i <= r; ++i)
    {
        for (int j = 1; j <= c; ++j)
        {
            if (a[i][j] >= value)
                bit2d_update(i, j, +1);
            
            if (i >= h && j >= w)
            {
                int cnt = bit2d_area_query(i - h + 1, j - w + 1, i, j);
                if (cnt >= target)
                    return true;
            }
        }
    }

    return false;
}

int subtask6()
{
    int expected = (h * w + 1) / 2;
    int upper = r * c - expected + 1;
    int lower = expected;

    int res = -1;
    for (int l = lower, r = upper; l <= r; )
    {
        int m = (l + r) >> 1;
        if (testing(m, expected))
        {
            maximize(res, m);
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }
    
    return res;
}

---

Hướng dẫn subtask 7

Nhận thấy là mình mỗi lần kiểm tra đều phải duyệt qua hết các phần tử và cũng chẳng cập nhật giá trị, nên việc sử dụng cây là không cần thiết.

Vậy mình chỉ cần dựng mảng cộng dồn

$2$ chiều thay cho cây để giảm bớt

$O(\log (r\times c))$ thành

$O(1)$.

---

Code

Time:

$O(r\times c\times \log (r\times c))$
Space:

$O(r\times c)$
Algo: Prefix Sum, Binary Search

Code

int subtask7()
{
    int expected = (h * w + 1) / 2;
    int upper = r * c - expected + 1;
    int lower = expected;

    int res = -1;

    for (int l = lower, r = upper; l <= r; )
    {
        int m = (l + r) >> 1;
        if (check(m, expected))
        {
            maximize(res, m);
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }
    
    return res;
}

---

Tổng hợp

Thực tế thì mình chỉ cần subtask

$7$ để giải toàn bộ các subtask con.

Mặc dù code rất đơn giản nhưng để hình thành ý tưởng thì phải có bước nhận xét về tính chất trung vị để chặt nhị phân

Nếu không có bước nhận xét từ trò của Fenwick Tree thì thực ra vẫn có thể thấy nếu ta tìm được cách đủ nhanh để kiểm tra

Time:

$O(subtask)$
Space:

$O(r\times c)$
Algo: Brute-forces, Data Structure, Binary Search, Sorting, Implementation, Sliding Window

Code

#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 3030;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }

int r, c, h, w;
int a[LIM][LIM];

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int subtask1() 
{ 
    return r * c; 
}
    
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int subtask2()
{ 
    return (r * c + 1) / 2;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int value[LIM * LIM];
int subtask3()
{
    int res = 0;
    for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
    {
        for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
        {
            int p = 0;
            for (int x = lx; x <= rx; ++x)
                for (int y = ly; y <= ry; ++y)
                    value[++p] = a[x][y];

            sort(value + 1, value + p + 1);
            maximize(res, value[(p + 1) / 2]);
        }
    }

    return res;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int used[LIM * LIM];
int subtask4()
{
    int timer = 0;
    memset(used, 0, sizeof(used));

    int res = 0;
    for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
    {
        for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
        {
            int mn = r * c;
            int mx = 1;
            ++timer;
            for (int x = lx; x <= rx; ++x)
            {
                for (int y = ly; y <= ry; ++y)
                {
                    minimize(mn, a[x][y]);
                    maximize(mx, a[x][y]);
                    used[a[x][y]] = timer;
                }
            }

            int cnt = (h * w + 1) / 2;
            for (int v = mn; v <= mx; ++v)
            {
                if (used[v] == timer)
                {
                    if (--cnt == 0)
                    {
                        maximize(res, v);
                        break;
                    }
                }
            }
        }
    }

    return res;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int bit[LIM * LIM];
void bit_construct()
{
    memset(bit, 0, sizeof(bit[0]) * (r * c + 1));
}

void bit_update(int p, int v)
{
    for (; p <= r * c; p += p & -p)
        bit[p] += v;
}

int bit_query(int p)
{
    int res = 0;
    for (; p >= 1; p -= p & -p)
        res += bit[p];

    return res;
}

int bit_median()
{
    int expected = (h * w + 1) / 2;
    int upper = r * c - expected + 1;
    int lower = expected;

    int res = -1;
    for (int l = lower, r = upper; l <= r; )
    {
        int m = (l + r) >> 1;
        if (bit_query(m) >= expected)
        {
            res = m;
            r = m - 1;
        }
        else 
        {
            l = m + 1;
        }
    }

    return res;
}

int subtask5()
{
    int res = 0;
    for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
    {
        bit_construct();
        for (int x = lx; x <= rx; ++x)
            for (int y = 1; y <= w; ++y)
                bit_update(a[x][y], +1);   

        for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
        {
            maximize(res, bit_median());

            if (ry == c) break;
            for (int x = lx; x <= rx; ++x)
            {
                bit_update(a[x][ly + 0], -1);
                bit_update(a[x][ry + 1], +1);
            }
        }
    }

    return res;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int bit2d[LIM][LIM];
void bit2d_construct()
{
    for (int x = 1; x <= r; ++x)
        memset(bit2d[x], 0, sizeof(bit2d[x][0]) * (c + 1));
}

void bit2d_update(int x, int y, int v)
{
    for (int p = x; p <= r; p += p & -p)
        for (int q = y; q <= c; q += q & -q)
            bit2d[p][q] += v;
}

int bit2d_query(int x, int y)
{
    int res = 0;
    for (int p = x; p >= 1; p -= p & -p)
        for (int q = y; q >= 1; q -= q & -q)
            res += bit2d[p][q];

    return res;
}

void bit2d_area_update(int x, int y, int u, int v, int k)
{
    bit2d_update(u, v, +k);
    bit2d_update(u, y - 1, -k);
    bit2d_update(x - 1, v, -k);
    bit2d_update(x - 1, y - 1, +k);
}

int bit2d_area_query(int x, int y, int u, int v)
{
    int res = 0;
    res += bit2d_query(u, v);
    res -= bit2d_query(u, y - 1);
    res -= bit2d_query(x - 1, v);
    res += bit2d_query(x - 1, y - 1);
    return res;
}

int testing(int value, int target)
{
    bit2d_construct();
    for (int i = 1; i <= r; ++i)
    {
        for (int j = 1; j <= c; ++j)
        {
            if (a[i][j] >= value)
                bit2d_update(i, j, +1);
            
            if (i >= h && j >= w)
            {
                int cnt = bit2d_area_query(i - h + 1, j - w + 1, i, j);
                if (cnt >= target)
                    return true;
            }
        }
    }

    return false;
}

int subtask6()
{
    int expected = (h * w + 1) / 2;
    int upper = r * c - expected + 1;
    int lower = expected;

    int res = -1;
    for (int l = lower, r = upper; l <= r; )
    {
        int m = (l + r) >> 1;
        if (testing(m, expected))
        {
            maximize(res, m);
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }
    
    return res;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int b[LIM][LIM];
int check(int value, int target)
{
    for (int i = 1; i <= r; ++i)
    {
        for (int j = 1; j <= c; ++j)
        {
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            b[i][j] += (a[i][j] >= value);
        }
    }

    for (int lx = 1, rx = h; rx <= r; ++lx, ++rx)
    {
        for (int ly = 1, ry = w; ry <= c; ++ly, ++ry)
        {
            int cnt = b[rx][ry] - b[lx - 1][ry] - b[rx][ly - 1] + b[lx - 1][ly - 1];
            if (cnt >= target)
                return true;
        }
    }

    return false;
}

int subtask7()
{
    int expected = (h * w + 1) / 2;
    int upper = r * c - expected + 1;
    int lower = expected;

    int res = -1;

    for (int l = lower, r = upper; l <= r; )
    {
        int m = (l + r) >> 1;
        if (check(m, expected))
        {
            maximize(res, m);
            l = m + 1;
        }
        else 
        {
            r = m - 1;
        }
    }
    
    return res;
}

/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    cin >> r >> c >> h >> w;
    if (h == 1 && w == 1) return cout << subtask1(), 0;
    if (h == r && w == c) return cout << subtask2(), 0;
    for (int i = 1; i <= r; ++i)
        for (int j = 1; j <= c; ++j)
            cin >> a[i][j];

    if (r <=   30 && c <=   30) return cout << subtask3(), 0;
    if (r <=  100 && c <=  100) return cout << subtask4(), 0;
    if (r <=  300 && c <=  300) return cout << subtask5(), 0;
    if (r <= 1000 && c <= 1000) return cout << subtask6(), 0;
    if (r <= 3000 && c <= 3000) return cout << subtask7(), 0;
    return 0;
}

---

Bonus

• Giả sử có truy vấn thay đổi giá trị
  $a_{i,j}$ thành
  $v$ thì bạn có thể làm được bài này không, giả sử giới hạn nhỏ hơn ?
• Giả sử có truy vấn trên môt bảng có góc trái dưới
  $[x,y]$ và góc phải trên
  $[u,v]$ thì bạn làm được trong độ phức tạp bao nhiêu ?