#6270. 数据结构板子题

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Moiezen

题目描述

n 个区间,第 i 个区间是 [l_i,r_i] ,它的长度是 r_i-l_i

q 个询问,每个询问给定 L,R,K ,询问被 [L,R] 包含的且长度不小于 K 的区间数量。

你想,像这种板子题,你随手写,不到十分钟就能 AC。

输入格式

第一行,两个空格隔开的正整数 n,q

接下来 n 行,第 i 行有两个空格隔开的正整数 l_i,r_i

接下来 q 行,每行三个空格隔开的正整数 L,R,K ,表示一个询问。

输出格式

q 行,每行一个非负整数,表示询问的答案。

样例

样例输入

5 5
1 2
1 3
2 3
2 4
2 5
1 5 1
1 4 1
1 5 2
2 5 2
1 5 3

样例输出

5
4
3
2
1

数据范围与提示

对于 30\% 的数据, n,q\leq5,000

对于 60\% 的数据, n,q\leq50,000

对于所有数据, n,q\leq500,000 l_i,r_i,L,R,K\leq n l_i<r_i L<R