###### tags: `TanKhoa`
# Queue, Deque

## queue
vào một đầu, ra đầu kia.
giống như em đi xếp hàng

queue<int> qu;
qu.push(x);
qu.pop();
int đầu = qu.top();
int độ_dài = qu.size()
bool có_rỗng_không = qu.empty();

# deque - hàng đợi 2 đầu
vào đầu nào cũng được, ra đầu nào cũng được nốt

deque có 2 đầu: đầu `front` và đầu `back`

deque<int> dq;
dq.push_front(x); dq.push_back(x);
dq.pop_front();   dq.pop_back();
int đầu = dq.front(), cuối = dq.back();
int độ_dài = dq.size();
bool có_rỗng_không = dq.empty();

## Xây dựng mảng
**Khuyến cáo:** thay vì đặt $b[i] = a[j]$ gần nhất, chúng ta đặt $b[i] = j$ gần nhất, tức là mình lưu vị trí thay vì giá trị.
Vì khi lưu vị trí, đồng thời chúng ta biết luôn giá trị, nhưng khi lưu giá trị, thì chưa biết được vị trí ở đâu hết.
### Cày trâu

for (int i = 1; i <= n; i++)
    for (int j = i - 1; j >= 0; j--)
        if (a[j] <= a[i]){
            b[i] = j; break;
        }
for (int i =1; i <= n; i++) cout << a[b[i]] << ' ';

### Thuật chuẩn
Giả sử có $a[i] = 7$.
Giờ xét tiếp $a[i+1] = 8$, ta thấy phần tử phía trước nhỏ hơn nên $b[i + 1] = a[i] = 7$.
Xét tiếp $a[i + 2] = 3$. Ta thấy là cả $a[i]$ lẫn $a[i + 1]$ đều lớn hơn $a[i + 2]$, vì vậy ta tạm thời loại bỏ 2 phần tử này.

Nếu thêm một phần tử $a[i + 3]$ nữa phía sau:
- Nếu nó $\ge 3 \rightarrow b[i+3] = 3$
- Nếu nó $< 3 \rightarrow$ loại bỏ $a[i+2]$ lẫn $a[i]\& a[i+1]$.

$\Rightarrow$ một phần tử một khi đã bị loại bỏ thì loại luôn, không cần xét lại nữa.

Vậy thuật toán của chúng ta sẽ là:
- Tạo stack rỗng
- Với mỗi phần tử $a[i]$
- Nếu stack rỗng => đáp án = 0
- Nếu không rỗng
- nếu đầu stack $\le a[i] \Rightarrow b[i] =$ đầu stack
- Còn không, pop số đó ra và xét số khác cho tới khi rỗng.
- cuối cùng, cho $a[i]$ vào stack

stack<int> st;
for (int i = 1; i <= n; i++){
    while(st.empty() == false and a[st.top()] > a[i]) st.pop();
    if (st.empty()) b[i] = 0;
    else b[i] = a[st.top()];
    st.push(i);
}

## Hình chữ nhật lớn nhất
Với mỗi cột, chúng ta cần tìm cách kéo dài sang hai bên nhiều nhất có thể.
Khi xét cột $i$, chúng ta chỉ dừng khi gặp một cột $j$ có $h[j] < h[i]$, khi đó, dù những cột sau có cao hơn, ta cũng không tới được.
$\Rightarrow$ chúng ta đang cần tìm cột ở bên trái và phải GẦN NHẤT sao cho nó nhỏ hơn hẳn $a[i]$.
$\Rightarrow$ làm bài Xây dựng mảng 2 lần.

Lưu ý: vì chúng ta cần xét cho cả 2 màu, nên:
- Lượt 1: xét mảng $h$
- Lượt 2: $h[i] = m - h[i]$, sau đó xét lại mảng

long long dtln()
    int nearL[500001] = {}, nearR[500001] = {};
    stack<int> st;
    for (int i = 1; i <= n; i++)
        while (st.empty() == false and a[st.top()] >= a[i]) st.pop();
        if (st.empty()) nearL[i] = 0;
        else nearL[i] = st.top();
    
    while (st.empty() == false) st.pop();
    for (int i = n; i >= 1; i--)
        while (st.empty() == false and a[st.top()] >= a[i]) st.pop();
        if (st.empty()) nearR[i] = n + 1;
        else nearR[i] = st.top();

    long long ans = 0;
    for (int i = 1; i <= n; i++)
        l = nearL[i] + 1; r = nearR[i] - 1;
        dt = (r-l+1) * h[i];
        ans = max(ans, dt);
    return ans;

a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a