Guest User

4498.cpp

a guest
Jul 4th, 2018
234
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cassert>
  5.  
  6. typedef long long ll;
  7.  
  8. struct Info { // Структура для хранения информации об отрезке
  9.     ll sum, pref, suff, max; // сумма элементов, максимальная сумма на префиксе, на суффиксе и на отрезке соответственно.
  10. };
  11.  
  12. // Функция комбинирования двух структур:
  13. Info combine(const Info& a, const Info& b) {
  14.     Info c{a.sum + b.sum, a.pref, b.suff, a.sum + b.sum};
  15.     c.pref = std::max(c.pref, a.sum + b.pref);
  16.     c.suff = std::max(c.suff, a.suff + b.sum);
  17.     c.max = std::max({a.suff + b.pref, c.sum, c.pref, c.suff, a.max, b.max});
  18.     return c;
  19. }
  20.  
  21. struct Node { // Структура под узел дерева отрезков
  22.     int vl, vr;
  23.    
  24.     Info info;
  25. };
  26.  
  27. struct SegmentTree {
  28.    
  29.     const int size;            // Размер исходного массива, над которым построено дерево отрезков
  30.    
  31.     std::vector<int> version;  // Массив различных версий дерева отрезков. Хранит корни дерева для соответствующей версии.
  32.    
  33.     std::vector<Node> data;    // Массив узлов дерева отрезков
  34.    
  35.     void build(int v, int l, int r, const std::vector<int>& arr) {
  36.         if (l == r) {
  37.             // Построение листа:
  38.             auto& curr = data[v];
  39.             curr.vl = curr.vr = -1;
  40.             curr.info = Info{arr[l], arr[l], arr[l], arr[l]};
  41.         } else {
  42.             int m = (l + r) / 2;
  43.             // Построение левого поддерева:
  44.             int vl = data[v].vl = data.size();
  45.             data.push_back(Node{});
  46.             build(vl,   l, m, arr);
  47.             // Построение правого поддерева:
  48.             int vr = data[v].vr = data.size();
  49.             data.push_back(Node{});
  50.             build(vr, m+1, r, arr);
  51.             // Объединение информации от поддеревьев:
  52.             data[v].info = combine(data[vl].info, data[vr].info);
  53.         }
  54.     }
  55.    
  56.     // Изменение отдельного элемента для выбранной версии:
  57.     void set(int v, int l, int r, int pos, int value) {
  58.         if (l == r) {
  59.             data[v].info = Info{value,value,value,value};
  60.         } else {
  61.             int m = (l + r) / 2, vl = data[v].vl, vr = data[v].vr;
  62.             if (pos <= m) { // Меняем левое поддерево:
  63.                 data.push_back(data[vl]);
  64.                 vl = data[v].vl = (int)data.size()-1;
  65.                 set(vl,   l, m, pos, value);
  66.             } else { // Меняем правое поддерево:
  67.                 data.push_back(data[vr]);
  68.                 vr = data[v].vr = (int)data.size()-1;
  69.                 set(vr, m+1, r, pos, value);
  70.             }
  71.             // Комбинируем ответы:
  72.             data[v].info = combine(data[vl].info, data[vr].info);
  73.         }
  74.     }
  75.    
  76.     // Изменение отдельного элемента с добавлением новой версии:
  77.     void set(int pos, int value) {
  78.         // Добавляем новую версию дерева:
  79.         data.push_back(data[version.back()]);
  80.         version.push_back((int)data.size()-1);
  81.         // Вызываем рекурсивную процедуру добавления пути в дереве:
  82.         set(version.back(), 0, size-1, pos, value);
  83.     }
  84.    
  85.     // Запрос к выбранной версии:
  86.     Info get(int v, int l, int r, int ql, int qr) {
  87.         if (l == ql && r == qr) {
  88.             return data[v].info;
  89.         } else {
  90.             int m = (l + r) / 2, vl = data[v].vl, vr = data[v].vr;
  91.             if (qr <= m) {       // Запрос лежит целиком в левом поддереве
  92.                 return get(vl,   l, m, ql, qr);
  93.             } else if (ql > m) { // Запрос лежит целиком в правом поддереве
  94.                 return get(vr, m+1, r, ql, qr);
  95.             } else {             // Разбиваем запрос на два, комбинируя ответы:
  96.                 return combine(get(vl, l, m, ql, m), get(vr, m+1, r, m+1, qr));
  97.             }
  98.         }
  99.     }
  100.    
  101.     // Запрос с выбором версии:
  102.     ll get(int idVersion, int left, int right) {
  103.         // Вызываем запрос для нужной версии:
  104.         return get(version[idVersion], 0, size-1, left, right).max;
  105.     }
  106.    
  107.     SegmentTree(const std::vector<int>& arr) : size((int)arr.size()){
  108.         // Изначальная версия - нулевая. Строим изначальную версию на массиве arr:
  109.         version.push_back(0);
  110.         data.push_back(Node{});
  111.         build(0, 0, size-1, arr);
  112.     }
  113.    
  114. };
  115.  
  116. int main() {
  117.     std::ios_base::sync_with_stdio(false);
  118.     std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0);
  119.    
  120.     int nItems, nDays;
  121.     std::cin >> nItems >> nDays;
  122.    
  123.     std::vector<int> arr(nItems);
  124.     for (auto& it : arr) {
  125.         std::cin >> it;
  126.     }
  127.    
  128.     // Строим дерево отрезков:
  129.     SegmentTree st(arr);
  130.    
  131.     // Заводим массив контроля версий под конец каждого дня:
  132.     std::vector<int> version(1+nDays, -1);
  133.     version[0] = 0;
  134.    
  135.     // Читаем запросы на изменение и добавляем новые версии дерева отрезков:
  136.     int nSetQueries;
  137.     std::cin >> nSetQueries;
  138.    
  139.     while (nSetQueries--) {
  140.         int day, pos, value;
  141.         std::cin >> day >> pos >> value;
  142.         version[day] = (int)st.version.size();
  143.         st.set(pos-1, value);
  144.     }
  145.    
  146.     // В промежуточные дни ссылаемся на версии предыдущих дней:
  147.     for (int i = 1; i <= nDays; ++i) {
  148.         if (version[i] == -1) {
  149.             version[i] = version[i-1];
  150.         }
  151.     }
  152.    
  153.     // Обрабатываем запросы:
  154.     int nGetQueries; ll answ = 0;
  155.     std::cin >> nGetQueries;
  156.     for (int i = 1; i <= nGetQueries; ++i) {
  157.         int l, r; std::cin >> l >> r;
  158.         int day = (i + answ) % nDays + 1;
  159.         answ = 0;
  160.         std::cout << (answ = std::max(answ, st.get(version[day], l-1, r-1))) << '\n';
  161.     }
  162.     return 0;
  163. }
RAW Paste Data