#include #include #include #include //#include using namespace std; struct Range { const int start; const int end; bool Include(const Range& inner) const { return start <= inner.start && inner.end <= end; } bool Exclude(const Range& inner) const { return end < inner.start || inner.end < start; } bool IsSingle() const { return start == end; } bool IsEmpty() const { return start > end; } }; struct NodeData { int64_t sum; int64_t left_max; int64_t right_max; int64_t in_max; bool empty = false; NodeData operator+(const NodeData& right) { if (empty) return right; if (right.empty) return *this; int64_t sum = this->sum + right.sum; int64_t left_max = max(max(this->left_max, this->sum + right.left_max), sum); int64_t right_max = max(max(this->right_max + right.sum, right.right_max), sum); int64_t in_max = max(this->right_max + right.left_max ,max(max(left_max, right_max), max(this->in_max, right.in_max))); return { sum , left_max, right_max, in_max }; } int64_t GetMaximum() const { return in_max; } static NodeData Empty; static NodeData Negative; }; NodeData NodeData::Empty = { 0,0,0,0, true }; NodeData NodeData::Negative = { -1e9,-1e9 ,-1e9 ,-1e9 }; class Node { private: const Range range; Node* left = nullptr; Node* right = nullptr; NodeData* data; public: Node(int s, int e, const int* init) : range(s, e) { if (range.IsSingle()) { data = new NodeData{ init[s] ,init[s],init[s] ,init[s] }; return; } int mid = (s + e) >> 1; left = new Node(s, mid, init); right = new Node(mid + 1, e, init); data = new NodeData(*left->data + *right->data); } NodeData QueryMax(const Range& query) const { if (query.Exclude(range)) return NodeData::Empty; if (query.Include(range)) return *data; return left->QueryMax(query) + right->QueryMax(query); } int64_t QuerySum(const Range& query) const { if (query.Exclude(range)) return 0; if (query.Include(range)) return data->sum; return left->QuerySum(query) + right->QuerySum(query); } ~Node() { delete left; delete right; } }; int sum(int64_t* prefix_sum, int s, int e) { if (s-- == 0) return prefix_sum[e]; return prefix_sum[e] - prefix_sum[s]; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int n; cin >> n; int* init = new int[n]; for (int i = 0;i < n;i++) { cin >> init[i]; } Node root(0, n - 1, init); int64_t* prefix_sum = new int64_t[n]; prefix_sum[0] = init[0]; for (int i = 1;i < n;i++) { prefix_sum[i] = prefix_sum[i - 1] + init[i]; } int q; cin >> q; while (q-- > 0) { int a_start, a_end, b_start, b_end; cin >> a_start >> a_end >> b_start >> b_end; a_start--; a_end--; b_start--; b_end--; int64_t result; if (a_end <= b_start) { int64_t mid = sum(prefix_sum, a_end, b_start); //NodeData middle = { mid ,mid ,mid ,mid }; const NodeData left = root.QueryMax({ a_start, a_end - 1 }); const NodeData right = root.QueryMax({ 1 + b_start,b_end }); result = max( max(left.right_max + mid, mid), max(right.left_max + mid, left.right_max + mid + right.left_max) ); } else { const NodeData overlap = root.QueryMax({ b_start + 1, a_end - 1 }); //제외 가능 const NodeData left = root.QueryMax({ a_start, b_start }); //오른쪽 한개 필수 const NodeData right = root.QueryMax({ a_end, b_end }); //왼쪽 한개 필수 result = max( max( max(left.right_max, left.right_max + overlap.left_max), max(overlap.right_max + right.left_max, right.left_max) ), max( left.right_max + overlap.sum + right.left_max, root.QueryMax({b_start, a_end}).GetMaximum() ) ); //cout << format("left range: {}~{}, right range: {}~{}, overlap: {}~{}\n", a_start, b_start, a_end, b_end, b_start + 1, a_end - 1); //cout << format("left.right_max: {}\nleft.right_max + overlap.left_max: {}\noverlap.right_max + right.left_max: {}\nright.left_max: {}\nleft.right_max + overlap.sum + right.left_max: {}\n", left.right_max, left.right_max + overlap.left_max, overlap.right_max + right.left_max, right.left_max, left.right_max + overlap.sum + right.left_max); } cout << result << '\n'; } }

제출 #78733

제출 정보

제출 결과

제출 코드

찾은 반례