#include <bits/stdc++.h> #define ll long long #define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i) #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define all(x) begin(x), end(x) #define endl '\n' using namespace std; const int MAX = 1e6 + 5; // Tăng lên gấp đôi vì mình sẽ nhân đôi mảng int n; int a[MAX]; // Input ban đầu ll sum[MAX]; // Mảng tổng cửa sổ trượt (Prefix sum cũng được) void solve() { // 1. Nhân đôi mảng để xử lý vòng tròn dễ hơn // a[0]...a[n-1] -> a[0]...a[2n-1] for(int i = 0; i < n; ++i) a[i + n] = a[i]; // Độ dài cửa sổ mà Hacker tác động (thường là N/2) int window = (n + 1) / 2; // 2. Tính tổng của mọi cửa sổ độ dài `window` // s là biến cộng dồn tạm thời ll s = 0; // Tính cửa sổ đầu tiên [0...window-1] for(int i = 0; i < window; ++i) s += a[i]; sum[0] = s; // Tính các cửa sổ tiếp theo bằng Sliding Window O(N) // sum[i] là tổng của đoạn bắt đầu từ i: a[i]...a[i+window-1] for(int i = 1; i < 2 * n; ++i) { s -= a[i - 1]; // Bỏ phần tử cũ if (i + window - 1 < 2 * n) // Kiểm tra biên s += a[i + window - 1]; // Thêm phần tử mới sum[i] = s; } // 3. Dùng Deque tìm Min/Max tùy theo đề bài // Giả sử logic của bạn là: Tìm max của (min các cửa sổ sum trong phạm vi nào đó) // Code dưới đây giữ nguyên logic logic "Max of Mins" của bạn deque<int> q; // Lưu chỉ số vector<ll> b(n * 2, -1e18); // Lưu kết quả // Cần xác định rõ phạm vi sliding window của bước 2 // Ví dụ: Với mỗi vị trí i, xét các đoạn sum trong khoảng [i, i + k...] // Ở đây mình minh họa khung sườn, bạn lắp logic phạm vi vào nhé /* LƯU Ý: Đoạn logic dưới này phụ thuộc vào việc Hacker xóa đoạn nào. Nếu Hacker xóa đoạn độ dài L bắt đầu tại j sao cho i thuộc đoạn đó? Hay Hacker xóa đoạn bất kỳ? Thường bài này là: Total_Sum - (Max sum đoạn con độ dài L). Nhưng nếu code bạn dùng queue để tìm min/max cục bộ thì áp dụng vào đây. */ // Demo Logic Deque chuẩn: int query_range = n - window + 1; // Ví dụ độ dài phạm vi query for (int i = 0; i < n * 2; ++i) { // 1. Pop phần tử quá hạn ra khỏi đầu hàng đợi if (!q.empty() && q.front() < i - query_range + 1) q.pop_front(); // 2. Duy trì tính đơn điệu (Giả sử tìm MIN thì pop các thằng LỚN hơn) while (!q.empty() && sum[q.back()] >= sum[i]) q.pop_back(); // 3. Push hiện tại vào q.push_back(i); // 4. Lấy kết quả (Min trong cửa sổ hiện tại) if (i >= query_range - 1) { // sum[q.front()] chính là min sum trong phạm vi // logic của bạn ở đây... } } } void input() { cin >> n; REP(i, n) cin >> a[i]; } int main() { ios::sync_with_stdio(0); cin.tie(0); // openFile("hacker"); // Nếu nộp bài cần file input(); solve(); }