Разбор

Заведем массив — счетчик $cnt$. Для каждого запроса $[l,r]$ выполним две операции: $cnt[l]++$ и $cnt[r+1]--$. Таким образом, частичная сумма $\sum _{j=1}^{i}cnt[j]$ будет равна количеству монет в $i$-ой копилке.

Количество дней, в которые Рой совершает действия, не превышает $10^6$. Каждый день он кладет в каждую копилку не более одной монеты. После выполнения всех действий в каждой копилке будет находиться не более $10^6$ монет. Заведем массив $coins$ размера $10^6$ и занесем в $coins[i]$ количество копилок с суммой $i$. Для этого для каждой частичной суммы $sum=\sum _{j=1}^{i}cnt[j]$ положим $coins[sum]++$.

Вычислим количество копилок, которые содержат как минимум $x$ монет. Для этого в массиве $coins$ пересчитаем его частичные суммы справа налево (то есть с конца). Тогда количество копилок, которые содержат как минимум $x$ монет, будет равно $coins[x]$.

Пример

Получим следующее распределение монет по копилкам:

Количество копилок с суммой $s$. Частичные суммы (подсчитанные справа налево) содержат количество копилок, содержащих как минимум $s$ монет.

Имеются одна копилка с суммой $0$ (копилка номер $7$), две копилки с суммой $1$ (копилки номер $4$ и $6$), три копилки с суммой $2$ (копилки номер $1,3$ и $5$), одна копилка с суммой $3$ (копилка номер $2$).

Вычислив частичные суммы массива $coins$, можно утверждать, например, что существует $6$ копилок, содержащих как минимум $1$ монету. Или что существует $4$ копилки, содержащих как минимум $2$ монеты.

Реализация алгоритма

Объявим рабочие массивы.

#define MAX 1000010
int cnt[MAX], coins[MAX];

Читаем входные данные. Строим массив $cnt$.

scanf("%d %d",&n,&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d",&l,&r);
  cnt[l]++; cnt[r+1]--;
}

В переменной $sum$ подсчитываем частичные суммы массива $cnt$. $i$-ая частичная сумма равна количеству монет в $i$-ой копилке. $coins[i]$ равно количеству копилок с суммой $i$.

sum = 0;
for(i = 1; i <= n; i++)
{
  sum += cnt[i];
  coins[sum]++;
}

В массиве $coins$ пересчитаем его частичные суммы справа налево.

for(i = MAX - 2; i >= 0; i--)
  coins[i] += coins[i+1];

Читаем количество запросов $q$. Для каждого запроса читаем значение $x$ и выводим ответ $coins[x]$.

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d",&x);
  printf("%d\n",coins[x]);
}

Python реализация

Объявим рабочие списки.

MAX = 1000010
cnt = [0] * MAX
coins = [0] * MAX

Читаем входные данные.

n = int(input())
m = int(input())

Строим список $cnt$.

for _ in range(m):
  l, r = map(int, input().split())
  cnt[l] += 1
  cnt[r + 1] -= 1

В переменной $sum$ подсчитываем частичные суммы списка $cnt$. $i$-ая частичная сумма равна количеству монет в $i$-ой копилке. $coins[i]$ равно количеству копилок с суммой $i$.

sum = 0
for i in range(1, n + 1):
  sum += cnt[i]
  coins[sum] += 1

В массиве $coins$ пересчитаем его частичные суммы справа налево.

for i in range(MAX - 2, -1, -1):
  coins[i] += coins[i + 1]

Читаем количество запросов $q$. Для каждого запроса читаем значение $x$ и выводим ответ $coins[x]$.

q = int(input())
for _ in range(q):
  x = int(input())
  print(coins[x])