#P9980. 数字加减

    ID: 8202 传统题 15000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-事件驱动模拟优先队列调度事件有序集合区间合并懒删除坐标变换增量维护同时事件分阶段处理2024“钉耙编程”中国大学生算法设计超级联赛(6)

数字加减

数字加减

Problem Description

你有一个整数 ss,初始时 s=0s = 0。每秒钟你可以在以下两个操作中选择执行至多一个:s:=s+1s := s + 1 或 s:=s−1s := s - 1(可以不执行任何一个)。ss 需要满足 nn 个限制,第 ii 个限制是在 tit_i 时刻末 ss 不能在 [li,ri][l_i, r_i] 范围内。 你需要回答 qq 个询问,第 ii 次询问给出一个时刻 ti′t'_i,你需要回答第 ti′t'_i 时刻末在满足限制的情况下 ss 有多少种可能的取值(只需要考虑 ti′t'_i 时刻末之前的限制即可)。

Input

第一行一个整数 TT(1≤T≤6001 \le T \le 600),表示测试数据的组数。 对于每组数据,第一行两个整数 nn 和 qq(1≤n,q≤5×1051 \le n,q \le 5 \times 10^5),分别表示限制个数和询问个数。 接下来 nn 行,第 ii 行三个整数 ti,li,rit_i,l_i,r_i(1≤ti≤109,−109≤li≤ri≤1091\le t_i\le 10^9,-10^9 \le l_i \le r_i \le 10^9),分别表示限制的时刻和限制范围。保证满足 1≤t1<t2<…<tn≤1091 \le t_1 < t_2 < \ldots < t_n \le 10^9。 接下来一行 qq 个整数 t1′,t2′,…,tq′t'_1, t'_2, \ldots, t'_q(1≤t1′<t2′<…<tq′≤1091 \le t'_1 < t'_2 < \ldots < t'_q \le 10^9),依次表示第 11 到第 qq 个询问的时刻。 保证所有测试数据的 nn、qq 之和均不超过 10610^6。

Output

对于每组测试数据,输出一行 qq 个整数,第 ii 个整数表示第 ii 个询问的答案。

Sample Input

2
2 3
3 -1 1
5 -2 0
2 3 5
2 2
4 -2 2
5 -10 10
3 5

Sample Output

5 4 8
7 0

Source

2024“钉耙编程”中国大学生算法设计超级联赛(6)