Почему моя реализация дерева сегментов не работает для тестов края и производительности при вычислении площади прямоугол ⇐ JAVA

[Anonymous]

Описание проблемы:
Нам дан список (выровненных по оси) прямоугольников. Каждый прямоугольник = [x1, y1, x2, y2], где (x1, y1) — координаты нижнего левого угла, а (x2, y2) — координаты верхнего правого угла i-го прямоугольника. Нам нужно найти общую площадь, занимаемую всеми прямоугольниками на плоскости. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Примечание: y1 всегда будет 0 .

Формат ввода:

• < li>Первая строка содержит целое число N — количество прямоугольников.
• Следующие N строк содержат по четыре целых числа: x1, y1, x2, y2.
  < /li>

Формат вывода:

Вывести общую площадь покрытия по модулю 10^9 + 7.

Ограничения:

• 1 end || start > r || end < l) return;
  
  if (start >= l && end 0) ? (end - start + 1) : 0;
  if (start != end) {
  lazy[2 * node + 1] += lazy[node];
  lazy[2 * node + 2] += lazy[node];
  }
  return;
  }
  
  int mid = (start + end) / 2;
  update(2 * node + 1, start, mid, l, r, val);
  update(2 * node + 2, mid + 1, end, l, r, val);
  tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
  }
  
  public long query(int l, int r) {
  return query(0, 0, size - 1, l, r);
  }
  
  private long query(int node, int start, int end, int l, int r) {
  if (lazy[node] != 0) {
  tree[node] = (lazy[node] > 0) ? (end - start + 1) : 0;
  if (start != end) {
  lazy[2 * node + 1] += lazy[node];
  lazy[2 * node + 2] += lazy[node];
  }
  lazy[node] = 0;
  }
  
  if (start > end || start > r || end < l) return 0;
  
  if (start >= l && end
• Мой ленивый логика распространения может быть ошибочной в некоторых случаях.
• Производительность неоптимальна для более крупных тестовых случаев.

Выполненные шаги по отладке:

• Зарегистрированные сжатые координаты.
• Запись отсортированных событий.
• Запись расчетов и сегментов промежуточной площади состояние дерева.
• Проверено ленивое распространение путем проверки состояний дерева вручную.

Вопрос: Что я делаю неправильно при реализации дерева сегментов? Может ли быть логический недостаток в ленивом распространении или обработке событий? Если да, то как я могу это исправить? Альтернативно, существует ли более эффективный подход к решению этой проблемы?

Подробнее здесь: https://stackoverflow.com/questions/792 ... -test-case