Hướng dẫn giải của Fency Fence
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; }