Hướng dẫn giải của Fency Fence


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

1. Ý tưởng thuật toán

Áp dụng kỹ thuật đếm theo Contribution. Với mỗi cột ~i~, ta sẽ đếm xem có bao nhiêu hình chữ nhật hợp lệ nhận ~h_i~ làm chiều cao lớn nhất có thể của nó.

Để làm điều này, ta cần tìm một khoảng ~[l, r]~ dài nhất chứa ~i~ sao cho mọi cột trong khoảng này đều có chiều cao ~\ge h_i~.

Số lượng hình chữ nhật bị giới hạn bởi cột ~i~ chính là: (Số đoạn thẳng ngang vắt qua cột ~i~ trong đoạn ~[l, r]~) ~\times~ (Số đoạn thẳng dọc tạo bởi chiều cao ~h_i~).

2. Xử lý đếm trùng

Nếu có nhiều cột có cùng chiều cao ~h~ liền kề nhau, việc mở rộng cả hai phía với điều kiện ~\ge h_i~ sẽ khiến các hình chữ nhật vắt qua nhiều cột cùng chiều cao bị đếm lặp lại nhiều lần.

~\Rightarrow~ Hình chữ nhật sẽ chỉ được đếm tại cột thấp nhất nằm ngoài cùng bên phải của nó. Cụ thể:

  • Mảng ~L[i]~ tìm cột gần nhất bên trái có ~h < h_i~.

  • Mảng ~R[i]~ tìm cột gần nhất bên phải có ~h \le h_i~.

Thao tác này ta sẽ dùng kỹ thuật Monotonic Stack để đạt độ phức tạp ~O(N)~.

3. Công thức tổ hợp và bao hàm loại trừ

Gọi khoảng mở rộng hợp lệ của cột ~i~ là đoạn từ ~l = L[i] + 1~ đến ~r = R[i] - 1~.

  • Tổng chiều rộng của cả đoạn: ~W_{total} = prefixW[r] - prefixW[l - 1]~. Tổng số đoạn ngang có thể tạo ra là ~C(W_{total})~.

  • Tuy nhiên, ta chỉ tính các đoạn ngang bắt buộc phải chứa (vắt qua) cột ~i~. Ta lấy tổng số đoạn trừ đi những đoạn không chứa ~i~:

  • Số đoạn nằm hoàn toàn bên trái cột ~i~: ~C(prefixW[i - 1] - prefixW[l - 1])~.

  • Số đoạn nằm hoàn toàn bên phải cột ~i~: ~C(prefixW[r] - prefixW[i])~.

Công thức: $$vắt\_ngang\_qua = C(W_{total}) - C(W_{left}) - C(W_{right})$$

Số lượng hình chữ nhật do cột ~i~ đóng góp sẽ là: $$contribution = vắt\_ngang\_qua \times C(h_i)$$

4. Độ phức tạp

  • Thời gian (Time Complexity): ~O(N)~. Monotonic Stack đảm bảo mỗi phần tử chỉ được đẩy vào stack 1 lần và lấy ra tối đa 1 lần trong cả 2 vòng for (tìm ~L~ và ~R~). Việc tính toán ở bước cuối là ~O(1)~ cho mỗi ~i~.

  • Không gian (Space/Memory): ~O(N)~.

Code tham khảo: Solution tại Ideone

#include <bits/stdc++.h>
#define Chris "test"
#define Fast std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
#define File(Chris) if(std::fopen(Chris".inp", "r")){std::freopen(Chris".inp", "r", stdin);std::freopen(Chris".out", "w", stdout);}
template<class X, class Y>bool maximize(X &x, const Y &y){if(x < y){x = y; return true;} else return false;}
template<class X, class Y>bool minimize(X &x, const Y &y){if(x > y){x = y; return true;} else return false;}
static constexpr long long mod = 1e9 + 7;
static constexpr long long INF = (long long) 2e9;
static constexpr int MAXN = (int) 1e5 + 5;
void add(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}

int numCol;
long long height[MAXN], width[MAXN];

long long calcC2(long long val) {
    long long a = val;
    long long b = val + 1;
    if (a % 2 == 0) a /= 2;
    else b /= 2;
    return (a % mod) * (b % mod) % mod;
}

void Inp(){
    std::cin >> numCol;
    for (int i = 1; i <= numCol; ++i) std::cin >> height[i];
    for (int i = 1; i <= numCol; ++i) std::cin >> width[i];
}

void Solve() {
    Inp();
    std::vector<std::pair<long long, long long>> st;
    int sumHW = 0;
    int ans = 0;

    for (int i = 1; i <= numCol; ++i) {
        int accWidth = 0;
        while (!st.empty() && st.back().first >= height[i]) {
            long long prevH = st.back().first;
            long long prevW = st.back().second;
            st.pop_back();

            int term = prevW * calcC2(prevH) % mod;
            add(sumHW, mod - term);
            add(accWidth, prevW);
        }

        long long curW = width[i] % mod;
        long long waysH = calcC2(height[i]);

        // 1. Hình chữ nhật ghép từ các đoạn phía trước có chiều cao < height[i]
        add(ans, curW * sumHW % mod);

        // 2. Hình chữ nhật ghép từ các đoạn phía trước bị ép chiều cao xuống height[i]
        add(ans, curW * accWidth % mod * waysH % mod);

        // 3. Hình chữ nhật nằm trọn bên trong đoạn i
        add(ans, calcC2(width[i]) * waysH % mod);

        // Đẩy khối đã gộp vào Stack
        int newWidth = accWidth;
        add(newWidth, curW);
        st.push_back({height[i], newWidth});
        add(sumHW, 1LL * newWidth * waysH % mod);
    }

    std::cout << ans << '\n';
    return;
}

signed main() {
    Fast
    File(Chris)
    Solve();
    return 0;
}

Đang tải...