Problem G: 木条染色

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $84$ 正确数量 $20$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 模拟 数据结构

小明是一个非常浪漫的画家,他喜欢画各种奇奇怪怪的画,虽然没人理解他画的究竟是什么东西。

有一天,他突发奇想,对于一根木条,他每次从木条中选取一个区间[l,r]进行染色,经过多次染色后,他想知道在[a,b]区间中有几个未被染色的子区间?

可惜小明虽然画画非常厉害,但是并不擅长解决这类问题,于是,他拿着这根木条来找你,希望你能够给他帮助。

假设木条无限长,所有查询都在木条长度范围内,未被染色的子区间是指,木条上染过色的区间的间断部分。

第一行一个整数T,代表数据组数。

对于每组数据,第一行给出两个整数n,q,分别代表染色的区间个数,以及查询个数。

之后n行,每行两个整数l,r,表示将l到r的区间进行染色,包含l,r两个节点。

之后q行,每行两个整数a,b,表示询问a到b总共有多少未被染色的子区间。

两组数据之间用一个空行隔开。

T<20

n<10000

q<100000

0<=l<r<1000000

0<=a<=b<1000000

对于每次询问,输出一个整数,表示查询结果。

每组数据之后,请输出一个空行。

2
2 3
1 2
3 4
1 3
3 4
5 5
3 3
1 5
2 8
5 6
0 5
0 9
9 9
1
0
1

1
2
1

对于第一组数据,[0,1),(2,3),(4,+)是未染色的子区间,因此查询[1,3]可以找到(2,3)这个子区间,而对于[3,4]不能找到,对于[5,5]可以找到[5,5]。

对于第二组数据,[0,1)和(8,+)是未染色的子区间,因此对于[0,5]只有子区间[0,1),对于查询[0,9],有子区间[0,1)和(8,9],对于查询[9,9],有[9,9]这个子区间。