桌子上零散地放着若干个盒子，盒子都平行于墙。桌子的后方是一堵墙。如图所示。现在从桌子的前方射来一束平行光， 把盒子的影子投射到了墙上。问影子的总宽度是多少？

输入格式

第1行：3个整数L，R，N。-100000 ≤L≤R≤ 100000，表示墙所在的区间；1≤N≤100000，表示盒子的个数 接下来N行，每行2个整数BL, BR，-100000 ≤BL≤BR≤ 100000，表示一个盒子的左、右端点

输出格式

第1行：1个整数W，表示影子的总宽度。

样例输入

Sample Input 1

0 7 2

1 2

4 5

Sample Input 2

-10 10 2

-5 2

-2 2

Sample Input 3

-10 10 3

-7 0

-4 9

-4 2

Sample Input 4

-100 100 3

-7 2

5 9

2 5

Sample Input 5

-50 50 4

-2 4

0 6

9 10

-5 30

样例输出

Sample Output 1

2

Sample Output 2

7

Sample Output 3

16

Sample Output 4

16

Sample Output 5

35

题解

用线段树维护左闭右开的区间 [l,r)影子的总宽度，标记flag表示这段区间是否全被影子覆盖。下传标记的时候，传完后不能置为0。

回忆前一题，每添加一个盒子，就会把线段树的一些区间完全覆盖，那么我们倒过来，从n到1添加盒子，在添加第i个盒子前，线段树上被覆盖的区间就是被挡住看不到的区间。要判断一个盒子能不能被看到，只要在这个盒子覆盖区间之前，判断一下要被覆盖的区间是不是已经被完全覆盖，如果没有被完全覆盖，这个盒子就可以被看到。