Phân tầng theo nhiều khoảng - EP1 (Layer Selection with Multiple Intervals - EP1)

Phiên bản: Phước Hưng OJ Extended

Đề bài

Các vị trí được đánh số bằng các số nguyên dương $1,2,3,\ldots$.

Với mỗi số nguyên dương $k$, vị trí $x$ thuộc tầng $k$ khi và chỉ khi

Do đó mỗi vị trí thuộc đúng một tầng.

Cho đoạn vị trí $[L,R]$ và $N$ khoảng tầng $[A_i,B_i]$. Một vị trí $x$ được chọn nếu chỉ số tầng chứa $x$ thuộc ít nhất một trong các khoảng tầng đã cho. Các khoảng có thể giao nhau, chứa nhau hoặc kề nhau.

Hãy đếm số vị trí được chọn trong $[L,R]$. Mỗi vị trí chỉ được tính một lần, kể cả khi tầng của nó được bao phủ bởi nhiều khoảng.

Input

• Dòng đầu chứa ba số nguyên $L,R,N$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $A_i,B_i$ mô tả khoảng tầng thứ $i$.

Output

In một số nguyên duy nhất: số lượng vị trí $x \in [L,R]$ được chọn.

Subtask

• Subtask 1 (25 điểm): $N \le 100$ và $R-L \le 10^5$.
• Subtask 2 (30 điểm): $R-L \le 10^6$.
• Subtask 3 (45 điểm): $1 \le L \le R \le 10^{18}$, $1 \le N \le 2\cdot10^5$, $1 \le A_i \le B_i \le 10^9$.

Ví dụ

Ví dụ 1

Input

1 20 2
2 2
3 3

Output

12

Giải thích

Tầng 2 gồm các vị trí từ 4 đến 8, tầng 3 gồm các vị trí từ 9 đến 15. Hai tầng tạo thành đoạn liên tiếp $[4,15]$ có 12 vị trí.

Ví dụ 2

Input

10 30 2
4 4
2 2

Output

9

Giải thích

Tầng 2 nằm trong $[4,8]$ nên không giao $[10,30]$. Tầng 4 nằm trong $[16,24]$, toàn bộ 9 vị trí này đều được tính.

Ví dụ 3

Input

1 100 3
2 4
4 6
8 8

Output

62

Giải thích

Hai khoảng $[2,4]$ và $[4,6]$ giao nhau, nên hợp của chúng là các tầng từ 2 đến 6. Các tầng này tương ứng với đoạn vị trí $[4,48]$ có 45 vị trí. Tầng 8 tương ứng với $[64,80]$ có 17 vị trí. Tổng là $45+17=62$.

Ví dụ 4

Input

50 70 2
1 3
8 10

Output

7

Giải thích

Các tầng 1 đến 3 kết thúc trước vị trí 50. Các tầng 8 đến 10 bắt đầu tại 64, nên chỉ đoạn $[64,70]$ nằm trong $[50,70]$, gồm 7 vị trí.

Ví dụ 5

Input

1000000000000000000 1000000000000000000 1
1000000000 1000000000

Output

1

Giải thích

$10^{18}=(10^9)^2$, nên vị trí duy nhất trong đoạn thuộc tầng $10^9$ và được tính đúng một lần.