Độ dài hợp các đoạn thẳng động

Buổi 27 — Segment Tree cơ bản
Points
55
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Ban đầu có một đa tập hợp rỗng các đoạn thẳng trên trục số. Cho $q$ thao tác:

  • 1 L R: Thêm đoạn $[L, R]$ vào đa tập hợp.
  • 2 L R: Xóa một đoạn $[L, R]$ khỏi đa tập hợp (đảm bảo đoạn này đang tồn tại).

Sau mỗi thao tác, hãy in ra tổng độ dài phần trục số được phủ bởi ít nhất một đoạn thẳng trong đa tập hợp.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $q$.
  • $q$ dòng tiếp theo, mỗi dòng mô tả một thao tác.
Dữ liệu ra

In ra $q$ dòng, dòng thứ $i$ là tổng độ dài phần bị phủ sau thao tác thứ $i$.

Ví dụ
Input Output
5
1 1 5
1 3 8
2 1 5
1 6 10
2 3 8
4
7
5
7
4
Giới hạn
  • $1 \le q \le 10^5$
  • $0 \le L < R \le 10^9$
Draft saved