C++を使用する以上およびそれ以上のクエリ

この記事では、問題が与えられ、配列が与えられ、答える必要のあるクエリには2つのタイプがあります。

• タイプ0 − x（与えられた値）以上の要素の数を計算する必要があります。
• タイプ1 − x（与えられた値）よりも厳密に大きい要素の数を計算する必要があります。

簡単な例を次に示します-

Input : arr[] = { 10, 15, 30 , 40, 45 } and Q = 3
   Query 1: 0 50
   Query 2: 1 40
   Query 3: 0 30
Output :
   0
   1
   3
Explanation:
x = 50, q = 0 : No elements greater than or equal to 50.
x = 40, q = 1 : 45 is greater than 40.
x = 30, q = 0 : three elements 30, 40, 45 are greater than or equal to 30.

解決策を見つけるためのアプローチ

2つの異なる方法を使用して解決策を見つけることができます。まず、ブルートフォースソリューションを使用してから、より高い制約で機能するかどうかを確認します。そうでない場合は、ソリューションの最適化に進みます。

ブルートフォースアプローチ

このアプローチでは、すべてのqクエリの配列をトラバースし、指定された条件を満たす番号を見つけます。

例

#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
   int count = 0; // answer
   if(!type) { // when type 0 query is asked
      for(int i = 0; i < n; i++) {
         if(arr[i] >= val)
            count++;
      }
   } else { // when type 1 query is asked
      for(int i = 0; i < n; i++) {
         if(arr[i] > val)
            count++;
      }
   }
   cout << count << "\n";
}
int main() {
   int ARR[] = { 10, 15, 30, 40, 45 };
   int n = sizeof(ARR)/sizeof(ARR[0]); // size of our array
   query(ARR, n, 0, 50); // query 1
   query(ARR, n, 1, 40); // query 2
   query(ARR, n, 0, 30); // query 3
   return 0;
}

出力

0
1
3

上記のアプローチでは、配列をトラバースしてクエリの回答を計算しているだけです。このアプローチは特定の例で機能しますが、より高い制約が発生した場合、プログラムの全体的な時間計算量はO（N * Q）であり、Nは配列のサイズ、Qはクエリの数であるため、このアプローチは失敗します。そこで、このアプローチを最適化して、より高い制約でも機能するようにします。

効率的なアプローチ

このアプローチでは、バイナリ検索を使用して、指定された値の上限と下限を見つけます。最初に二分探索を使用して配列を並べ替え、次にそれに応じて下限関数と上限関数を適用します。

例

#include <bits/stdc++.h>

using namespace std;
void lowerbound(int *arr, int n, int val) {
   int l = -1, r = n;
   while(r - l > 1) { // binary searching the answer
      int mid = (l+r)/2;
      if(arr[mid] >= val)
         r = mid;
      else
         l = mid;
   }
   if(r == n) // if r is unmoved then it means there is no element that satisfy the condition
      cout << "0\n";
   else
      cout << n - r << "\n";
}
void upperbound(int *arr, int n, int val) {
   int l = -1, r = n;
   while(r - l > 1) { // binary searching the answer
      int mid = (l+r)/2;
      if(arr[mid] > val)
         r = mid;
      else
         l = mid;
   }
   if(r == n)// if r is unmoved then it means there is no element that satisfy the condition
      cout << "0\n";
   else
      cout << n - r <<"\n";
}
void query(int *arr, int n, int type, int val) {
   if(!type) // if type == 0 we call lower bound function
      lowerbound(arr, n, val);
   else // if type == 1 we call upperbound function
      upperbound(arr, n, val);
}
int main() {
   int arr[] = { 1, 2, 3, 4 };
   int n = sizeof(arr)/sizeof(arr[0]); // size of our array
   sort(arr, arr+n); // sorting the array
   query(arr, n, 0, 5); // query 1
   query(arr, n, 1, 3); // query 2
   query(arr, n, 0, 3); // query 3
   return 0;
}

出力

0
1
2

上記のコードは、時間計算量を大幅に削減する二分探索で機能します。したがって、最終的な複雑さは O（NlogN）になります。 、ここで、Nは配列のサイズです。

上記のコードの説明

このアプローチでは、バイナリ検索を使用して、指定された値の上限と下限を見つけます。バイナリ検索では、ソートされた配列でのみ機能するため、最初に配列をソートします。配列を並べ替えたので、それぞれタイプ0、タイプ1の条件を満たす最初の数値を見つけるのに役立つ下限関数と上限関数を作成します。条件に役立つ最初の数値が見つかったため、この要素の後の要素も条件に従うため、この要素のインデックスとN（配列のサイズ）の差を出力します。

結論

この記事では、二分探索を使用する以上のクエリを解決するための問題を解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常および効率的）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。