API tools faq
paste
Advertisement
coloriot

HA46_2

coloriot
Mar 23rd, 2025
42
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.06 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h> // Удобный вызов всех библиотек
  2. using namespace std;
  3. using ll = long long; // Alias
  4.  
  5. // Каждый лист соответствует интервалу [comp[i], comp[i+1]) с весом = comp[i+1] - comp[i].
  6. // Операция обновления (на интервале) заключается в том, что для каждого элемента,
  7. // если его значение меньше B, то оно устанавливается в B, а прирост (B - старое_значение)
  8. // умножается на вес интервала и суммируется.
  9. struct SegmentTree {
  10.     int n; // количество листов (n = comp.size() - 1)
  11.     vector<int> comp; // сжатые координаты (отсортированы и уникальны)
  12.     vector<int> lazy; // "ленивые" обновления; -1 означает отсутствие обновления
  13.     vector<int> mn, mx; // минимальное и максимальное значение в сегменте
  14.     vector<ll> sum;    // взвешенная сумма значений в сегменте
  15.     vector<ll> weight; // суммарный вес сегмента
  16.  
  17.     SegmentTree(const vector<int>& comp_) : comp(comp_) {
  18.         n = comp.size() - 1; // число интервалов
  19.         lazy.assign(4 * n, -1);
  20.         mn.assign(4 * n, 0);
  21.         mx.assign(4 * n, 0);
  22.         sum.assign(4 * n, 0);
  23.         weight.assign(4 * n, 0);
  24.         build(1, 0, n - 1);
  25.     }
  26.  
  27.     // Построение дерева для узла idx, отвечающего за интервал [l, r]
  28.     void build(int idx, int l, int r) {
  29.         if(l == r) {
  30.             weight[idx] = (ll)comp[l + 1] - comp[l];
  31.             mn[idx] = 0;
  32.             mx[idx] = 0;
  33.             sum[idx] = 0;
  34.             lazy[idx] = 0; // начальное значение 0
  35.         } else {
  36.             int mid = (l + r) / 2;
  37.             build(idx * 2, l, mid);
  38.             build(idx * 2 + 1, mid + 1, r);
  39.             weight[idx] = weight[idx * 2] + weight[idx * 2 + 1];
  40.             mn[idx] = min(mn[idx * 2], mn[idx * 2 + 1]);
  41.             mx[idx] = max(mx[idx * 2], mx[idx * 2 + 1]);
  42.             sum[idx] = sum[idx * 2] + sum[idx * 2 + 1];
  43.             lazy[idx] = -1;
  44.         }
  45.     }
  46.  
  47.     // Применяет присваивание для узла idx: устанавливает все элементы в узле равными val.
  48.     void apply(int idx, int val) {
  49.         sum[idx] = (ll)val * weight[idx];
  50.         mn[idx] = val;
  51.         mx[idx] = val;
  52.         lazy[idx] = val;
  53.     }
  54.  
  55.     // Отталкивание ленивого обновления вниз (pushDown)
  56.     void pushDown(int idx) {
  57.         if(lazy[idx] != -1) {
  58.             apply(idx * 2, lazy[idx]);
  59.             apply(idx * 2 + 1, lazy[idx]);
  60.             lazy[idx] = -1;
  61.         }
  62.     }
  63.  
  64.     // Функция update_range обновляет сегмент [ql, qr] (индексы листьев) так, что
  65.     // для каждого элемента, если его значение меньше B, оно становится равным B.
  66.     // При этом общий прирост добавляется в переменную added.
  67.     void update_range(int idx, int l, int r, int ql, int qr, int B, ll &added) {
  68.         if(ql > r || qr < l) return;
  69.         if(ql <= l && r <= qr) {
  70.             // Если максимальное значение в сегменте меньше B, обновляем весь сегмент разом
  71.             if(mx[idx] < B) {
  72.                 ll newSum = (ll)B * weight[idx];
  73.                 added += newSum - sum[idx];
  74.                 apply(idx, B);
  75.                 return;
  76.             }
  77.             // Если минимальное значение в сегменте уже не меньше B, обновление не требуется
  78.             if(mn[idx] >= B) {
  79.                 return;
  80.             }
  81.         }
  82.         int mid = (l + r) / 2;
  83.         pushDown(idx);
  84.         update_range(idx * 2, l, mid, ql, qr, B, added);
  85.         update_range(idx * 2 + 1, mid + 1, r, ql, qr, B, added);
  86.         sum[idx] = sum[idx * 2] + sum[idx * 2 + 1];
  87.         mn[idx] = min(mn[idx * 2], mn[idx * 2 + 1]);
  88.         mx[idx] = max(mx[idx * 2], mx[idx * 2 + 1]);
  89.     }
  90.  
  91.     // Функция обновления: обновляет сегмент [ql, qr]
  92.     // и возвращает общий прирост.
  93.     ll update(int ql, int qr, int B) {
  94.         ll added = 0;
  95.         if(ql > qr) return 0;
  96.         update_range(1, 0, n - 1, ql, qr, B, added);
  97.         return added;
  98.     }
  99. };
  100.  
  101. // Структура PaintLine поддерживает префиксное обновление для одного квадрата.
  102. // Для данного квадрата строится сегментное дерево по "сжатой" оси x.
  103. struct PaintLine {
  104.     vector<int> comp; // сжатые x-координаты
  105.     SegmentTree seg;
  106.     PaintLine(const vector<int>& comp_) : comp(comp_), seg(comp_) {}
  107.    
  108.     // Функция updatePrefix обновляет префикс [0, A) значением B.
  109.     ll updatePrefix(int A, int B) {
  110.         int pos = int(lower_bound(comp.begin(), comp.end(), A) - comp.begin());
  111.         if(pos <= 0) return 0;
  112.         return seg.update(0, pos - 1, B);
  113.     }
  114. };
  115.  
  116. // Структура Snapshot описывает "снимок" с четырьмя координатами.
  117. // В оригинальной системе координат снимок покрывает прямоугольник с противоположными углами (x1, y1) и (x2, y2).
  118. struct Snapshot {
  119.     int x1, y1, x2, y2;
  120. };
  121.  
  122. int main(){
  123.     ios::sync_with_stdio(false);
  124.     cin.tie(nullptr);
  125.  
  126.     int n;
  127.     cin >> n;
  128.     vector<Snapshot> snaps(n);
  129.     for (int i = 0; i < n; i++){
  130.         cin >> snaps[i].x1 >> snaps[i].y1 >> snaps[i].x2 >> snaps[i].y2;
  131.     }
  132.    
  133.     // Для каждого квадрата собираем все x-координаты для обновления префикса.
  134.     // Для верхнего правого и нижнего правого квадратов используем s.x2;
  135.     // для верхнего левого и нижнего левого квадратов используем -s.x1.
  136.     vector<int> compTR, compTL, compBR, compBL;
  137.     compTR.push_back(0);
  138.     compTL.push_back(0);
  139.     compBR.push_back(0);
  140.     compBL.push_back(0);
  141.    
  142.     for (int i = 0; i < n; i++){
  143.         if(snaps[i].x2 > 0) {
  144.             compTR.push_back(snaps[i].x2);
  145.             compBR.push_back(snaps[i].x2);
  146.         }
  147.         if(snaps[i].x1 < 0) {
  148.             compTL.push_back(-snaps[i].x1);
  149.             compBL.push_back(-snaps[i].x1);
  150.         }
  151.     }
  152.    
  153.     auto compSortUnique = [&](vector<int>& vec) {
  154.         sort(vec.begin(), vec.end());
  155.         vec.erase(unique(vec.begin(), vec.end()), vec.end());
  156.     };
  157.     compSortUnique(compTR);
  158.     compSortUnique(compTL);
  159.     compSortUnique(compBR);
  160.     compSortUnique(compBL);
  161.    
  162.     // Создаем PaintLine для каждого квадрата, если в нем есть хотя бы один интервал.
  163.     unique_ptr<PaintLine> plTR, plTL, plBR, plBL;
  164.     if(compTR.size() >= 2) plTR = make_unique<PaintLine>(compTR);
  165.     if(compTL.size() >= 2) plTL = make_unique<PaintLine>(compTL);
  166.     if(compBR.size() >= 2) plBR = make_unique<PaintLine>(compBR);
  167.     if(compBL.size() >= 2) plBL = make_unique<PaintLine>(compBL);
  168.    
  169.     // Обрабатываем снимки в обратном порядке.
  170.     // Для каждого снимка суммируем "вклад" по четырем квадратам.
  171.     vector<ll> ans(n, 0);
  172.     for (int i = n - 1; i >= 0; i--){
  173.         ll cur = 0;
  174.         Snapshot s = snaps[i];
  175.         // Верхний правый квадрат: обновляем, если s.x2 > 0 и s.y2 > 0.
  176.         if(s.x2 > 0 && s.y2 > 0 && plTR) {
  177.             cur += plTR->updatePrefix(s.x2, s.y2);
  178.         }
  179.         // Верхний левый квадрат: преобразуем x как -s.x1; обновляем, если s.x1 < 0 и s.y2 > 0.
  180.         if(s.x1 < 0 && s.y2 > 0 && plTL) {
  181.             cur += plTL->updatePrefix(-s.x1, s.y2);
  182.         }
  183.         // Нижний правый квадрат: преобразуем y как -s.y1; обновляем, если s.x2 > 0 и s.y1 < 0.
  184.         if(s.x2 > 0 && s.y1 < 0 && plBR) {
  185.             cur += plBR->updatePrefix(s.x2, -s.y1);
  186.         }
  187.         // Нижний левый квадрат: преобразуем оба значения; обновляем, если s.x1 < 0 и s.y1 < 0.
  188.         if(s.x1 < 0 && s.y1 < 0 && plBL) {
  189.             cur += plBL->updatePrefix(-s.x1, -s.y1);
  190.         }
  191.         ans[i] = cur;
  192.     }
  193.    
  194.     // Выводим ответы для каждого снимка в исходном порядке.
  195.     for(auto a : ans)
  196.         cout << a << "\n";
  197.    
  198.     return 0;
  199. }
  200.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!