Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
数直線上に N 個の点があり,そのうち i 番目の点は座標 X_i にあります. これらの点は座標の昇順に番号がついています. つまり,すべての i (1 \leq i \leq N-1) について,X_i<X_{i+1} が成り立ちます. また,整数 K が与えられます.
Q 個のクエリを処理してください.
i 番目のクエリでは,整数 L_i,R_i が与えられます. ここで,点の集合 s がよい集合であるとは,以下の条件をすべて満たすことを意味します. よい集合の定義がクエリごとに変わることに注意してください.
- s に含まれる点は,X_{L_i},X_{L_i+1},\ldots,X_{R_i} のいずれかである.
- s に含まれるどの異なる 2 点についても,その間の距離が K 以上である.
- s のサイズは,上記の条件を満たす集合の中で最大である.
各クエリごとに,すべてのよい集合の和集合のサイズを求めてください.
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq X_1 <X_2 < \cdots < X_N \leq 10^9
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq L_i \leq R_i \leq N
- 入力は全て整数である.
入力
入力は以下の形式で標準入力から与えられる.
N K X_1 X_2 \cdots X_N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
各クエリごとに,すべてのよい集合の和集合のサイズを一行に出力せよ.
入力例 1
5 3 1 2 4 7 8 2 1 5 1 2
出力例 1
4 2
1 つめのクエリでは,最大 3 つの点を集合に含めることができます. よい集合は,\{1,4,7\} と \{1,4,8\} の 2 つです. よって,すべてのよい集合の和集合のサイズは |\{1,4,7,8\}|=4 です.
2 つめのクエリでは,最大 1 つの点を集合に含めることができます. よい集合は,\{1\} と \{2\} の 2 つです. よって,すべてのよい集合の和集合のサイズは |\{1,2\}|=2 です.
入力例 2
15 220492538 4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194 5 6 14 1 8 1 13 7 12 4 12
出力例 2
4 6 11 2 3
Score : 800 points
Problem Statement
There are N points on a number line, i-th of which is placed on coordinate X_i. These points are numbered in the increasing order of coordinates. In other words, for all i (1 \leq i \leq N-1), X_i < X_{i+1} holds. In addition to that, an integer K is given.
Process Q queries.
In the i-th query, two integers L_i and R_i are given. Here, a set s of points is said to be a good set if it satisfies all of the following conditions. Note that the definition of good sets varies over queries.
- Each point in s is one of X_{L_i},X_{L_i+1},\ldots,X_{R_i}.
- For any two distinct points in s, the distance between them is greater than or equal to K.
- The size of s is maximum among all sets that satisfy the aforementioned conditions.
For each query, find the size of the union of all good sets.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq L_i \leq R_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K X_1 X_2 \cdots X_N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
Output
For each query, print the size of the union of all good sets in a line.
Sample Input 1
5 3 1 2 4 7 8 2 1 5 1 2
Sample Output 1
4 2
In the first query, you can have at most 3 points in a good set. There exist two good sets: \{1,4,7\} and \{1,4,8\}. Therefore, the size of the union of all good sets is |\{1,4,7,8\}|=4.
In the second query, you can have at most 1 point in a good set. There exist two good sets: \{1\} and \{2\}. Therefore, the size of the union of all good sets is |\{1,2\}|=2.
Sample Input 2
15 220492538 4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194 5 6 14 1 8 1 13 7 12 4 12
Sample Output 2
4 6 11 2 3