题解

​ 简化一下题意：给定 $m$ 个区间 $[l_i,r_i]$ ，每次给该区间的所有数加上 1(初始值为0)，之后进行 $Q$ 次询问，每次询问坐标 $x$ 的值是多少。

​ 这样转化完之后就变成一维差分数组的板子题了，给 $a$ 数组中的 $[l, r]$ 区间中的每一个数都加上 $c$,只需对差分数组 $b$ 做 $b[l] + = c$, $b[r+1] - = c$。

​ 将差分数组转化为原数组只需对差分数组求前缀和即可。

代码

题目描述

小红拥有一片神秘的花园，花园中种满了奇花异草，每一种植物都有其独特的编号，从 0 到 $N$。小红为了研究稀有花卉的生长规律，每天都会在园中巡视。最近，他发现有些花卉的生长受到了未知因素的影响。经过观察，小红认为是每晚飞过花园的神秘飞鸟对这些植物造成了一定的影响。

每当夜晚，神秘飞鸟会从一个编号的区域飞到另一个编号的区域。每次飞过，它们都会经过一串连续编号的植物区域，并对这些植物进行神秘的歌唱，从而影响它们的生长。

多次观察后，小红记录下了每次飞鸟影响的植物区域的左右边界。现在他想知道，经过连续 $M$ 次飞鸟的夜间歌唱后，具体哪些编号的植物受到了多少次的影响。

输入描述

第一行包含两个正整数 $N$ 和 $M$，代表植物的编号范围和飞鸟歌唱的次数。

第二行共 $M$ 个空格分开的正整数 $L_1, L_2, ..., L_M$，表示每次飞鸟影响植物区域的左边界编号。

第三行共 $M$ 个空格分开的正整数 $R_1, R_2, ..., R_M$，表示每次飞鸟影响植物区域的右边界编号。

第四行一个正整数 $Q$，代表小红想要了解的植物编号数量。

第五行共 $Q$ 个空格分开的正整数，表示小红想要查询影响次数的植物编号。

输出描述

输出一行共 $Q$ 个数，用空格隔开，依次表示每个植物编号对应的飞鸟歌唱影响次数。

样例输入

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

样例输出

0 1 3 2 1

评测数据与规模

$1 \leq N, M, Q \leq 10^5$，$0 \leq L_i \leq R_i \leq N$。