---
author: nguyencter
tags: CMAT
title: CMAT Solution
---

$\Huge\text{CMAT Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/drive/folders/1vkCZtOGkj1EsipJw55kkjZ-Oq_3P5Gnu)
📌 Tags: `prefix`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

Cho một bảng số nguyên gồm $n$ hàng và $m$ cột và $Q$ thao tác mỗi thao tác được mô tả bằng bộ năm số $x,y,u,v,c$ mỗi thao tác sẽ tăng tất cả các phần tử 𝑎(𝑖,𝑗) với mọi 𝑥 ≤ 𝑖 ≤ 𝑢 , 𝑦 ≤ 𝑗 ≤ 𝑣 lên một lượng là 𝑐 (𝑐 > 0)

**Yêu cầu:** Cho bảng số và dãy $Q$ thao tác, tìm phần tử lớn nhất khi xóa đi đúng $1$ thao tác trong $Q$ thao tác đã cho.

-----

## Thuật toán

Gọi $max_a$ là phần tử lớn nhất của mảng sau khi thực hiện $Q$ thao tác.

Với mỗi thao tác ta $t$ sẽ tăng một vùng tương ứng lên $c_t$ đơn vị vì vậy nên $max_t$ của mảng khi trừ đi thao tác này sẽ là $max_t=max($phần tử lớn nhất ngoài vùng được tăng$,max_a-c)$

Để giảm thời gian tính toán ta dùng $2$ mảng prefixmax.

Gọi $preUL[i][j]$ là phần tử lớn nhất từ hàng $1$ đến $i$ và cột $1$ đến $j$.

Gọi $preDR[i][j]$ là phần tử lớn nhất từ hàng $i$ đến $n$ và cột $j$ đến $m$.

Kết quả là $max(max_1,max_2,...,max_q)$.

Độ phức tạp là $O(n*m+Q)$

----
Tham khảo code mẫu ở [đây](https://github.com/nguyencter/CODE/blob/main/cmat.cpp).