小明是一个非常浪漫的画家，他喜欢画各种奇奇怪怪的画，虽然没人理解他画的究竟是什么东西。
有一天，他突发奇想，对于一根木条，他每次从木条中选取一个区间[l,r]进行染色，经过多次染色后，他想知道在[a,b]区间中有几个未被染色的子区间？
可惜小明虽然画画非常厉害，但是并不擅长解决这类问题，于是，他拿着这根木条来找你，希望你能够给他帮助。
假设木条无限长，所有查询都在木条长度范围内，未被染色的子区间是指，木条上染过色的区间的间断部分。
1433: 木条染色
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $83$ | 正确数量 | $20$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 模拟 数据结构 |
Description
Input
第一行一个整数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
Output
对于每次询问，输出一个整数，表示查询结果。
每组数据之后，请输出一个空行。
Sample Input复制
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
Sample Output复制
1
0
1
1
2
1
提示
对于第一组数据，[0,1)，(2,3)，(4,+
)是未染色的子区间，因此查询[1,3]可以找到(2,3)这个子区间，而对于[3,4]不能找到，对于[5,5]可以找到[5,5]。
)是未染色的子区间，因此查询[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]这个子区间。
推荐代码 查看1433 所有题解 上传题解视频得图灵币
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$0 $ms] | 缚己 | 410431 | 2019-04-26 19:26:12 |
| 内存最少[$1388 $KB] | 罗瑞靖 | 428196 | 2019-05-15 10:22:11 |
| 第一AC | 毛裕锋@信息132 | 23074 | 2016-11-01 16:39:29 |
| 第一挑战 | 毛裕锋@信息132 | 23064 | 2016-11-01 16:22:13 |
赛题来源/所属竞赛 2016 Anhui College Student Programming Contest N/A
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|---|---|---|
| 1350 | 大学生程序设计大赛模拟赛3 | 2019-05-15 09:00:00 | 请登录 |