在给定子阵列中小于或等于给定数量的元素数-yiteyi-C++库

给定一个数组“a[]”和查询数q。每个查询可以用l、r、x表示。您的任务是打印由l到r表示的子数组中小于或等于x的元素数。

null

例如：

Input : arr[] = {2, 3, 4, 5}
            q = 2
            0 3 5
            0 2 2 
Output : 4
         1
Number of elements less than or equal to
5 in arr[0..3] is 4 (all elements)

Number of elements less than or equal to
2 in arr[0..2] is 1 (only 2)

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

天真的方法 每个查询的朴素方法遍历子数组并计算给定范围内的元素数。

有效的方法 这个想法是使用- 二叉索引树 .

注意：在下面的步骤中，x是一个数字，根据这个数字，你必须找到元素，子数组用l，r表示。步骤1：按升序对数组排序。第二步：按照x的升序对查询进行排序，将位数组初始化为0。第3步：从第一个查询开始，遍历数组，直到数组中的值小于等于x。对于每个这样的元素，更新值等于1的位第4步：查询l到r范围内的位数组

                     // C++ program to answer queries to count number                   
                     // of elements smaller tban or equal to x.                   
                     #include<bits/stdc++.h>                   
                     using                               namespace                               std;                   
                             
                     // structure to hold queries                   
                     struct                               Query                   
                     {                   
                                         int                               l, r, x, idx;                   
                     };                   
                             
                     // structure to hold array                   
                     struct                               ArrayElement                   
                     {                   
                                         int                               val, idx;                   
                     };                   
                             
                     // bool function to sort queries according to k                   
                     bool                               cmp1(Query q1, Query q2)                   
                     {                   
                                         return                               q1.x < q2.x;                   
                     }                   
                             
                     // bool function to sort array according to its value                   
                     bool                               cmp2(ArrayElement x, ArrayElement y)                   
                     {                   
                                         return                               x.val < y.val;                   
                     }                   
                             
                     // updating the bit array                   
                     void                               update(                               int                               bit[],                               int                               idx,                               int                               val,                               int                               n)                   
                     {                   
                                         for                               (; idx<=n; idx +=idx&-idx)                   
                                         bit[idx] += val;                   
                     }                   
                             
                     // querying the bit array                   
                     int                               query(                               int                               bit[],                               int                               idx,                               int                               n)                   
                     {                   
                                         int                               sum = 0;                   
                                         for                               (; idx > 0; idx -= idx&-idx)                   
                                         sum += bit[idx];                   
                                         return                               sum;                   
                     }                   
                             
                     void                               answerQueries(                               int                               n, Query queries[],                               int                               q,                   
                                         ArrayElement arr[])                   
                     {                   
                                         // initialising bit array                   
                                         int                               bit[n+1];                   
                                         memset                               (bit, 0,                               sizeof                               (bit));                   
                             
                                         // sorting the array                   
                                         sort(arr, arr+n, cmp2);                   
                             
                                         // sorting queries                   
                                         sort(queries, queries+q, cmp1);                   
                             
                                         // current index of array                   
                                         int                               curr = 0;                   
                             
                                         // array to hold answer of each Query                   
                                         int                               ans[q];                   
                             
                                         // looping through each Query                   
                                         for                               (                               int                               i=0; i<q; i++)                   
                                         {                   
                                         // traversing the array values till it                   
                                         // is less than equal to Query number                   
                                         while                               (arr[curr].val <= queries[i].x && curr<n)                   
                                         {                   
                                         // updating the bit array for the array index                   
                                         update(bit, arr[curr].idx+1, 1, n);                   
                                         curr++;                   
                                         }                   
                             
                                         // Answer for each Query will be number of                   
                                         // values less than equal to x upto r minus                   
                                         // number of values less than equal to x                   
                                         // upto l-1                   
                                         ans[queries[i].idx] = query(bit, queries[i].r+1, n) -                   
                                         query(bit, queries[i].l, n);                   
                                         }                   
                             
                                         // printing answer for each Query                   
                                         for                               (                               int                               i=0 ; i<q; i++)                   
                                         cout << ans[i] << endl;                   
                     }                   
                             
                     // driver function                   
                     int                               main()                   
                     {                   
                                         // size of array                   
                                         int                               n = 4;                   
                             
                                         // initialising array value and index                   
                                         ArrayElement arr[n];                   
                                         arr[0].val = 2;                   
                                         arr[0].idx = 0;                   
                                         arr[1].val = 3;                   
                                         arr[1].idx = 1;                   
                                         arr[2].val = 4;                   
                                         arr[2].idx = 2;                   
                                         arr[3].val = 5;                   
                                         arr[3].idx = 3;                   
                             
                                         // number of queries                   
                                         int                               q = 2;                   
                                         Query queries[q];                   
                                         queries[0].l = 0;                   
                                         queries[0].r = 2;                   
                                         queries[0].x = 2;                   
                                         queries[0].idx = 0;                   
                                         queries[1].l = 0;                   
                                         queries[1].r = 3;                   
                                         queries[1].x = 5;                   
                                         queries[1].idx = 1;                   
                             
                                         answerQueries(n, queries, q, arr);                   
                             
                                         return                               0;                   
                     }                   

输出：

1
4

本文由 阿尤什·贾哈 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章