ulvis.paste.net

Paste Search Dynamic
Recent pastes
struct
  1. /**
  2. Дан массив из целых чисел a1, a2, ..., an (индексация с 1!).
  3. Для каждого запроса [left, right] найдите такой подотрезок al, al+1, ...,
  4. ar этого массива (1 <= left <= l <= r <= right <= n), что сумма чисел al + al+1 + ... + ar
  5. является максимально возможной. Требуемое время ответа на запрос - O(log n).
  6. */
  7. #include <iostream>
  8. #include <vector>
  9.  
  10. struct Range {
  11.     int left;
  12.     int right;
  13.     Range(int _left, int _right);
  14.     bool In(int index) const; /// returns true if index in range
  15. };
  16.  
  17. bool Range::In(int index) const {
  18.     return left <= index && index <= right;
  19. }
  20.  
  21. Range::Range(int _left, int _right): left(_left), right(_right) {
  22.  
  23. }
  24.  
  25. struct Node {
  26.     int mid; /// max value of on subrange
  27.     int left; /// max sum on prefix
  28.     int right; /// max sum on suffix
  29.     int sum; /// sum on range
  30.     Range range;
  31.     Node(int _left, int _mid, int _right, int _sum, Range _range): right(_right), left(_left), mid(_mid), sum(_sum), range(_range) {
  32.  
  33.     }
  34. };
  35.  
  36. class do {
  37. public:
  38.     explicit do(std::vector<int>& _buffer);
  39.     int Get(int left, int right) const;
  40. private:
  41.     std::vector<Node> buffer;
  42.     Node GetNode(int left, int right, int index) const;
  43.     Node Merge(const Node& leftNode, const Node& rightNode) const;
  44. };
  45.  
  46. do::do(std::vector<int>& _buffer) {
  47.     int n = 1; /// leaf count (degree of 2)
  48.     while (n < _buffer.size()) {
  49.         n *= 2;
  50.     }
  51.     buffer.resize(2 * n - 1, Node(0, 0, 0, 0, Range(0, 0)));
  52.     /// initialization of leaves with values of _buffer
  53.     for (int i = n - 1; i < n + _buffer.size() - 1; ++i) {
  54.         int j = i - n + 1;
  55.         buffer[i] = Node(_buffer[j], _buffer[j], _buffer[j], _buffer[j], Range(j, j));
  56.     }
  57.     /// initialization of extra leaves with 0 values to summary count of n
  58.     for (int i = n + _buffer.size() - 1; i < buffer.size(); ++i) {
  59.         buffer[i] = Node(0, 0, 0, 0, Range(i - n + 1, i - n + 1));
  60.     }
  61.     /// initialization of non-leaf nodes of tree
  62.     for (int i = n - 2; i >= 0; --i) {
  63.         buffer[i] = Merge(buffer[2 * i + 1], buffer[2 * i + 2]);
  64.     }
  65. }
  66.  
  67. Node do::GetNode(int left, int right, int index) const {
  68.     if (buffer[index].range.left >= left && buffer[index].range.right <= right) {
  69.         /// range of node in range of query -> return this node
  70.         return buffer[index];
  71.     }
  72.     int leftSon = 2 * index + 1;
  73.     int rightSon = 2 * index + 2;
  74.     if (buffer[leftSon].range.In(left) && buffer[leftSon].range.In(right)) {
  75.         /// range of query in left son's range -> return left son's answer
  76.         return GetNode(left, right, leftSon);
  77.     }
  78.     if (buffer[rightSon].range.In(left) && buffer[rightSon].range.In(right)) {
  79.         /// range of query in right son's range -> return right son's answer
  80.         return GetNode(left, right, rightSon);
  81.     }
  82.     /// range of query concerns both left and right son
  83.     Node leftNode = GetNode(left, buffer[leftSon].range.right, leftSon);
  84.     Node rightNode = GetNode(buffer[rightSon].range.left, right, rightSon);
  85.     return Merge(leftNode, rightNode);
  86. }
  87.  
  88. int do::Get(int left, int right) const {
  89.     return GetNode(left, right, 0).mid;
  90. }
  91.  
  92. Node do::Merge(const Node& leftNode, const Node& rightNode) const {
  93.     /// returns initialization list for Node
  94.     return {
  95.         std::max(leftNode.left, leftNode.sum + rightNode.left), /// left
  96.         std::max(leftNode.right + rightNode.left, std::max(leftNode.mid, rightNode.mid)), /// mid
  97.         std::max(rightNode.right, rightNode.sum + leftNode.right), /// right
  98.         leftNode.sum + rightNode.sum, /// sum
  99.         Range(leftNode.range.left, std::min(rightNode.range.right, (static_cast<int>(buffer.size()) + 1) / 2)) ///range
  100.     };
  101. }
  102.  
  103. void Solve() {
  104.     int n, m;
  105.     while (std::cin >> n >> m) {
  106.         std::vector<int> v(n);
  107.         for (auto& i: v) {
  108.             std::cin >> i;
  109.         }
  110.         do d(v);
  111.         for (int i = 0; i < m; ++i) {
  112.             unsigned x, y;
  113.             std::cin >> x >> y;
  114.             --x; --y;
  115.             std::cout << d.Get(x, y) << std::endl;
  116.         }
  117.     }
  118. }
  119.  
  120.  
  121. int main() {
  122.     std::ios_base::sync_with_stdio(false);
  123.     Solve();
  124. }
Parsed in 0.028 seconds