查询相关问题的好算法 [英] Good algorithm for a query related problem
问题描述
给定 N 对，我们必须找到在其范围内包含元素 k 的对的计数，即:
如果一个 Pairi 被定义为 (Xi,Yi)，那么如果 Pairi 在它的范围，然后 Xi <= K <= Yi.
Given N pairs, we have to find the count of pairs that contain an element k in their range, i.e :
If a Pairi is defined as (Xi,Yi), then if Pairi contain K in its range, then Xi <= K <= Yi.
现在我们有 Q 个这样的查询来处理每个由整数 K 组成的查询.
Now we are given Q such queries to handle with each query consisting of an integer K.
输入:第一行包含两个空格分隔的整数 N 和 Q.
接下来是 N 行，每行表示一对.每行包含两个空格分隔的整数.
接下来 Q 行，每行表示一个整数 K
Input:
The first line contains two space-separated integers N and Q.
Next N lines follow where each line denotes a pair. Each line contains two space-separated integers.
Next Q lines follow where each line denotes an integer K
输出:我们将输出对的计数，其中 Xi i<= K <= Yi 对于每个查询
Output: We are to output the count of pairs where Xi i<= K <= Yi for each query
限制条件:1 <= N,Q <= 105
时间限制: 2 s
示例:
输入-
4 2
1 5
2 5
6 10
7 8
7
9
输出-
2
1
说明-
第一个查询 K=7 对 (6,10) 和 (7,8) 成立.
第二个查询 K=9 仅适用于 (6,10).
Input-
4 2
1 5
2 5
6 10
7 8
7
9
Output-
2
1
Explanation-
First query K=7 holds for (6,10) and (7,8).
Second query K=9 holds for (6,10) only.
下面给出了我的复杂度为 O(NQ) 的 Java 代码.
Given below is my code in java with complexity O(NQ).
import java.util.*;
class Query
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n,q;
n = sc.nextInt();
q = sc.nextInt();
int x[] = new int[n];
int y[] = new int[n];
for(int i=0;i<n;i++)
{
x[i] = sc.nextInt();
y[i] = sc.nextInt();
}
while(q-->0)
{
int k = sc.nextInt();
int count = 0;
for(int i = 0;i<n;i++)
{
if(x[i] <= k && k <= y[i])
count++;
}
System.out.println(count);
}
}
}
有人可以为我提供一种具有更好复杂性的方法，例如 O(N + Q log N)?我想过使用段树等，但如果它可以解决这个问题以及如何在这里实现它，我就没有考虑过.
Can somebody provide me with an approach that has a better complexity such as O(N + Q log N)? I thought of using segment trees and such but do not if it would work for this problem and how to implement it here.
推荐答案
通过在查询本身之前执行预处理可以获得复杂度 O(NlogN + QlogN).
A complexity O(NlogN + QlogN) can be obtained by performing a preprocessing before the queries themselves.
第一步:预处理
目标是确定每个区间的每个极限 A[k] 关联的区间数，并对这些 A[k] 进行排序.
The goal is to determine the number of intervals associated for each limit A[k] of each interval, and to sort these A[k].
这是通过以下方式执行的:对于每个输入区间[X, Y]，放置相应的限制X和Y在一个数组中，我们计算每个限制的开闭次数X:
This is performed in the following way: for each input interval [X, Y], the corresponding limits X and Y are put in a array, and we count the number of openings and closures for each limit X:
open[X] ++
close[Y] ++
背后的原因是X之后的每个值都获得"了一个区间，而Y之后的每个值都失去"了一个区间.
The reason behind is that each value after X is "gaining'" one interval, and each value after Y is "losing" one interval.
然后，排序后，递归得到给定极限的区间数:
Then, after sorting, the number of intervals of a given limit is obtained recursively:
After the limit: W[0] = n_opening[0], W[i] = W[i-1] + n_opening[i] - n_closure[i]
On the limit: WL[0] = n_opening[0], WL[i] = W[i-1] + n_opening[i]
通过一个例子可以更好地说明这一点.对于输入区间 [1,5], [2, 5], [6, 10], [7, 8]，V[] 值由下式给出:
This is better illustrated by an example. For the input intervals [1,5], [2, 5], [6, 10], [7, 8], the V[] values are given by:
open[] 1 1 0 1 1 0 0
close[] 0 0 2 0 0 1 1
---|---|---|---|---|---|---|---
1 2 5 6 7 8 10
而 W[] 和 WL[] 值由
And the W[] and WL[] values are provided by
WL[] 1 2 2 1 2 2 1
W[] 1 2 0 1 2 1 0
---|---|---|---|---|---|---|---
1 2 5 6 7 8 10
第二步:查询
对于每个查询K，我们首先要确定对应的区间[A[i], A[i+1]].由于 A[i] 已排序，这将在 log(N) 中完成.然后:
For each query K, we have first to determine the corresponding interval [A[i], A[i+1]]. As the A[i] are sorted, this an be done in log(N). Then:
If K is outside any interval: m[k] = 0
If K is in the interval ]A[i], A[i+1][, i.e. not equal to any limit, then m[k] = W[A[i]]
if K is equal to a limit A[i], then m[k] = WL[a[i]]
在前面的例子中:
K = 7 -> m(7) = WL[7] = 2
K = 9 -> m(9) = W[8] = 1
这篇关于查询相关问题的好算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
