#PU666. USACO 2016 December Contest, Silver — Problem 1. Counting Haybales

    ID: 1234 传统题 文件IO:haybales 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:dec16来源:usaco.orgscoring:equal_test_cases线段树

USACO 2016 December Contest, Silver — Problem 1. Counting Haybales

USACO 2016 December Contest, Silver — Problem 1. Counting Haybales

题目描述

Farmer John has just arranged his NN haybales (1≤N≤100,0001 \leq N \leq 100,000) at various points along the one-dimensional road running across his farm. To make sure they are spaced out appropriately, please help him answer QQ queries (1≤Q≤100,0001 \leq Q \leq 100,000), each asking for the number of haybales within a specific interval along the road.

输入格式

The first line contains NN and QQ. The next line contains NN distinct integers, each in the range 0…1,000,000,0000 \ldots 1,000,000,000, indicating that there is a haybale at each of those locations. Each of the next QQ lines contains two integers AA and BB (0≤A≤B≤1,000,000,0000 \leq A \leq B \leq 1,000,000,000) giving a query for the number of haybales between AA and BB, inclusive.

输出格式

You should write QQ lines of output. For each query, output the number of haybales in its respective interval.

数据范围

(见题面原文)

样例

样例 1

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10
2
2
3
4
1
0
Problem credits: Nick Wu